Academic literature on the topic 'Line graph'

Una decomposizione in cicli pari (ECD) di un grafo euleriano è una partizione dell'insieme degli spigoli in cicli pari. Coloriamo i cicli pari in modo che i cicli che condividono almeno un vertice ricevano colori distinti. Se m è il numero minimo di colori richiesti, allora diciamo che la decomposizione in cicli pari ha indice m. La nozione di ECD di indice m è connessa al palette index di un grafo, un parametro cromatico che descrive un grafo a partire dal numero minimo di palette dei suoi vertici. In particolare, i possibili valori per il palette index di un grafo 4-regolare sono 1, 3, 4 e 5. Il palette index è 3 se e solo se il grafico ha un 2-fattore pari o un ECD di indice 3. Esistono infinite famiglie di grafi 4-regolari con un ECD di indice 3 . Per quanto ne sappiamo, non è noto alcun esempio di grafo 4-regolare il cui insieme di spigoli può essere partizionato in cicli pari e ogni ECD ha indice maggiore di 3. Motivati dal problema sull'esistenza di un tale grafo 4-regolare, studiamo ECD in line graph 4-regolari di grafi cubici di classe 2. Per alcune delle infinite famiglie di grafi cubici di classe 2, caratterizzati da una grande oddness, possiamo trovare un ECD di indice 3 nel line graph corrispondente.<br>An even cycle decomposition (ECD) of an Eulerian graph is a partition of the edge-set into even cycles. We color the even cycles so as two cycles sharing at least one vertex receive distinct colors. If m is the minimum number of required colors, then we say that the even cycle decomposition has index m. The notion of an ECD of index m is connected to the palette index of a graph, a chromatic parameter describing a graph by the minimum number of palettes of its vertices. In particular, the possible values for the palette index of a 4-regular graph are 1, 3, 4 and 5. It is 3 if and only if the graph has an even 2-factor or an ECD of index 3. There exist infinite families of 4-regular graphs with an ECD of index 3 . As far as we know, no example of 4-regular graph whose edge set can be partitioned into even cycles and every ECDs has index larger than 3 is known. Motivated by the problem on the existence of such a 4-regular graph, we study ECDs in 4-regular line graphs of class 2 cubic graphs. For some of the infinite families of class 2 cubic graphs that are characterized by an arbitrary large oddness, we can find an ECD of index 3 in the corresponding line graph.

In this thesis, we focus on the following topics: supereulerian graphs, hamiltonian line graphs, fault-tolerant Hamiltonian laceability of Cayley graphs generated by transposition trees, and several extremal problems on the (minimum and/or maximum) size of graphs under a given graph property. The thesis includes six chapters. The first one is to introduce definitions and summary the main results of the thesis, and in the last chapter we introduce the furture research of the thesis. The main studies in Chapters 2 - 5 are as follows. In Chapter 2, we explore conditions for a graph to be supereulerian.In Section 1 of Chapter 2, we characterize the graphs with minimum degree at least 2 and matching number at most 3. By using the characterization, we strengthen the result in [93] and we also address a conjecture in the paper.In Section 2 of Chapter 2, we prove that if $d(x)+d(y)\geq n-1-p(n)$ for any edge $xy\in E(G)$, then $G$ is collapsible except for several special graphs, where $p(n)=0$ for $n$ even and $p(n)=1$ for $n$ odd. As a corollary, a characterization for graphs satisfying $d(x)+d(y)\geq n-1-p(n)$ for any edge $xy\in E(G)$ to be supereulerian is obtained. This result extends the result in [21].In Section 3 of Chapter 2, we focus on a conjecture posed by Chen and Lai [Conjecture~8.6 of [33]] that every 3-edge connected and essentially 6-edge connected graph is collapsible. We find a kind of sufficient conditions for a 3-edge connected graph to be collapsible.In Chapter 3, we mainly consider the hamiltonicity of 3-connected line graphs.In the first section of Chapter 3, we give several conditions for a line graph to be hamiltonian, especially we show that every 3-connected, essentially 11-connected line graph is hamilton- connected which strengthens the result in [91].In the second section of Chapter 3, we show that every 3-connected, essentially 10-connected line graph is hamiltonian-connected.In the third section of Chapter 3, we show that 3-connected, essentially 4-connected line graph of a graph with at most 9 vertices of degree 3 is hamiltonian. Moreover, if $G$ has 10 vertices of degree 3 and its line graph is not hamiltonian, then $G$ can be contractible to the Petersen graph.In Chapter 4, we consider edge fault-tolerant hamiltonicity of Cayley graphs generated by transposition trees. We first show that for any $F\subseteq E(Cay(B:S_{n}))$, if $|F|\leq n-3$ and $n\geq4$, then there exists a hamiltonian path in $Cay(B:S_{n})-F$ between every pair of vertices which are in different partite sets. Furthermore, we strengthen the above result in the second section by showing that $Cay(S_n,B)-F$ is bipancyclic if $Cay(S_n,B)$ is not a star graph, $n\geq4$ and $|F|\leq n-3$.In Chapter 5, we consider several extremal problems on the size of graphs.In Section 1 of Chapter 5, we bounds the size of the subgraph induced by $m$ vertices of hypercubes. We show that a subgraph induced by $m$ (denote $m$ by $\sum\limits_{i=0}^ {s}2^{t_i}$, $t_0=[\log_2m]$ and $t_i= [\log_2({m-\sum\limits_{r=0}^{i-1}2 ^{t_r}})]$ for $i\geq1$) vertices of an $n$-cube (hypercube) has at most $\sum\limits_{i=0}^{s}t_i2^{t_i-1} +\sum\limits_{i=0}^{s} i\cdot2^{t_i}$ edges. As its applications, we determine the $m$-extra edge-connectivity of hypercubes for $m\leq2^{[\frac{n}2]}$ and $g$-extra edge-connectivity of the folded hypercube for $g\leq n$.In Section 2 of Chapter 5, we partially study the minimum size of graphs with a given minimum degree and a given edge degree. As an application, we characterize some kinds of minimumrestricted edge connected graphs.In Section 3 of Chapter 5, we consider the minimum size of graphs satisfying Ore-condition.

In this thesis, we describe linear codes over prime fields obtained from incidence designs of iterated line graphs of complete graphs Li(Kn) where i = 1, 2. In the binary case, results are extended to codes from neighbourhood designs of the line graphs Li+1(Kn) using certain elementary relations. Codes from incidence designs of complete graphs, Kn, and neighbourhood designs of their line graphs, L1(Kn) (the so-called triangular graphs), have been considered elsewhere by others. We consider codes from incidence designs of L1(Kn) and L2(Kn), and neighbourhood designs of L2(Kn) and L3(Kn). In each case, basic parameters of the codes are determined. Further, we introduce a family of vertex-transitive graphs 􀀀n that are embeddable into the strong product L1(Kn) ⊠ K2, of triangular graphs and K2, a class which at first sight may seem unnatural but, on closer look, is a repository of graphs rich with combinatorial structures. For instance, unlike most regular graphs considered here and elsewhere that only come with incidence and neighbourhood designs, 􀀀n also has what we have termed as 6-cycle designs. These are designs in which the point set contains vertices of the graph and every block contains vertices of a 6-cycle in the graph. Also, binary codes from incidence matrices of these graphs have other minimum words in addition to incidence vectors of the blocks. In addition, these graphs have induced subgraphs isomorphic to the family Hn of complete porcupines (see Definition 4.11). We describe codes from incidence matrices of 􀀀n and Hn and determine their parameters.