The existence of even factors in iterated line graphs

An even factor of a graph is a spanning subgraph of G in which all degrees are even, positive integers. In this paper, we characterize the claw-free graphs having even factors and then prove that the n-iterated line graph Lⁿ(G) of G has an even factor if and only if every end branch of G has length at most n and every odd branch-bond of G has a branch of length at most n+1.     

Linkability in iterated line graphs

We prove that for every graph H with the minimum degree δ?5, the third iterated line graph L³(H) of H contains as a minor. Using this fact we prove that if G is a connected graph distinct from a path, then there is a number k_G such that for every i?k_G the i-iterated line graph of G is -linked. Since the degree of Lⁱ(G) is even, the result is best possible.     

Connectivity of iterated line graphs

Let k≥0 be an integer and L^k(G) be the kth iterated line graph of a graph G. Niepel and Knor proved that if G is a 4-connected graph, then κ(L²(G))≥4δ(G)−6. We show that the connectivity of G can be relaxed. In fact, we prove in this note that if G is an essentially 4-edge-connected and 3-connected graph, then κ(L²(G))≥4δ(G)−6. Similar bounds are obtained for essentially 4-edge-connected and 2-connected (1-connected) graphs.     

Planarity of iterated line graphs

The line index of a graph G is the smallest k such that the kth iterated line graph of G is nonplanar. We show that the line index of a graph is either infinite or it is at most 4. Moreover, we give a full characterization of all graphs with respect to their line index.     

Characterizations of second iterated line graphs

The main results of this paper are two characterizations of second iterated line graphs, i.e., two sets of necessary and sufficient conditions for the existence of solutions to the graph equation H = L²(G). A method to get a root of the graph equation is also given if one exists.     

Colouring graphs with bounded generalized colouring number

Given a graph G and a positive integer p, χ_p(G) is the minimum number of colours needed to colour the vertices of G so that for any i≤p, any subgraph H of G of tree-depth i gets at least i colours. This paper proves an upper bound for χ_p(G) in terms of the k-colouring number of G for k=2^p−2. Conversely, for each integer k, we also prove an upper bound for in terms of χ_k+2(G). As a consequence, for a class K of graphs, the following two statements are equivalent:

(a)

For every positive integer p, χ_p(G) is bounded by a constant for all G∈K.

(b)

For every positive integer k, is bounded by a constant for all G∈K.

It was proved by Nešet?il and Ossona de Mendez that (a) is equivalent to the following:

(c)

For every positive integer q, ∇_q(G) (the greatest reduced average density of G with rank q) is bounded by a constant for all G∈K.

Therefore (b) and (c) are also equivalent. We shall give a direct proof of this equivalence, by introducing ∇_q−(1/2)(G) and by showing that there is a function F_k such that . This gives an alternate proof of the equivalence of (a) and (c).     

Closure, stability and iterated line graphs with a 2-factor

We consider 2-factors with a bounded number of components in the n-times iterated line graph Lⁿ(G). We first give a characterization of graph G such that Lⁿ(G) has a 2-factor containing at most k components, based on the existence of a certain type of subgraph in G. This generalizes the main result of [L. Xiong, Z. Liu, Hamiltonian iterated line graphs, Discrete Math. 256 (2002) 407-422]. We use this result to show that the minimum number of components of 2-factors in the iterated line graphs Lⁿ(G) is stable under the closure operation on a claw-free graph G. This extends results in [Z. Ryjá?ek, On a closure concept in claw-free graphs, J. Combin. Theory Ser. B 70 (1997) 217-224; Z. Ryjá?ek, A. Saito, R.H. Schelp, Closure, 2-factors and cycle coverings in claw-free graphs, J. Graph Theory 32 (1999) 109-117; L. Xiong, Z. Ryjá?ek, H.J. Broersma, On stability of the hamiltonian index under contractions and closures, J. Graph Theory 49 (2005) 104-115].     

Connected graphs switching equivalent to their iterated line graphs

In this paper, the problem of determining graphs which are switching equivalent to at least one of their iterated line graphs is considered, and such connected graphs are characterized.     

Queue layouts of iterated line directed graphs

In this paper, we study queue layouts of iterated line directed graphs. A k-queue layout of a directed graph consists of a linear ordering of the vertices and an assignment of each arc to exactly one of the k queues so that any two arcs assigned to the same queue do not nest. The queuenumber of a directed graph is the minimum number of queues required for a queue layout of the directed graph.We present upper and lower bounds on the queuenumber of an iterated line directed graph L^k(G) of a directed graph G. Our upper bound depends only on G and is independent of the number of iterations k. Queue layouts can be applied to three-dimensional drawings. From the results on the queuenumber of L^k(G), it is shown that for any fixed directed graph G, L^k(G) has a three-dimensional drawing with O(n) volume, where n is the number of vertices in L^k(G). These results are also applied to specific families of iterated line directed graphs such as de Bruijn, Kautz, butterfly, and wrapped butterfly directed graphs. In particular, the queuenumber of k-ary butterfly directed graphs is determined if k is odd.     

Total interval number for graphs with bounded degree

The total interval number of an n-vertex graph with maximum degree Δ is at most (Δ + 1/Δ)n/2, with equality if and only if every component of the graph is K_Δ,Δ. If the graph is also required to be connected, then the maximum is Δn/2 + 1 when Δ is even, but when Δ is odd it exceeds [Δ + 1/(2.5Δ + 7.7)]n/2 for infinitely many n. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 79–84, 1997     

Generalized degree conditions for graphs with bounded independence number

We consider a generalized degree condition based on the cardinality of the neighborhood union of arbitrary sets of r vertices. We show that a Dirac-type bound on this degree in conjunction with a bound on the independence number of a graph is sufficient to imply certain hamiltonian properties in graphs. For K_1,m-free grphs we obtain generalizations of known results. In particular we show: Theorem. Let r ≥ 1 and m ≥ 3 be integers. Then for each nonnegative function f(r, m) there exists a constant C = C(r, m, f(r, m)) such that if G is a graph of order n (n ≥ r, n > m) with δ_r(G) ≥ (n/3) + C and β (G) ≥ f(r, m), then (a) G is traceable if δ(G) ≥ r and G is connected; (b) G is hamiltonian if δ(G) ≥ r + 1 and G is 2-connected; (c) G is hamiltonian-connected if δ(G) ≥ r + 2 and G is 3-connected. © 1995 John Wiley & Sons, Inc.     

On a conjecture about Wiener index in iterated line graphs of trees

Let $G$ be a graph. Denote by $L^i\left(G\right)$ its $i$-iterated line graph and denote by $W\left(G\right)$ its Wiener index. Dobrynin and Melnikov conjectured that there exists no nontrivial tree $T$ and $i\ge 3$, such that $W\left(L^i\left(T\right)\right)=W\left(T\right)$. We prove this conjecture for trees which are not homeomorphic to the claw $K_{1,3}$ and $H$, where $H$ is a tree consisting of 6 vertices, 2 of which have degree 3.     

Hamilton cycles and closed trails in iterated line graphs

Let G be an undirected connected graph that is not a path. We define h(G) (respectively, s(G)) to be the least integer m such that the iterated line graph L^m(G) has a Hamiltonian cycle (respectively, a spanning closed trail). To obtain upper bounds on h(G) and s(G), we characterize the least integer m such that L^m(G) has a connected subgraph H, in which each edge of H is in a 3-cycle and V(H) contains all vertices of degree not 2 in L^m(G). We characterize the graphs G such that h(G) — 1 (respectively, s(G)) is greater than the radius of G.     

Even subgraphs of bridgeless graphs and 2-factors of line graphs

By Petersen's theorem, a bridgeless cubic multigraph has a 2-factor. Fleischner generalised this result to bridgeless multigraphs of minimum degree at least three by showing that every such multigraph has a spanning even subgraph. Our main result is that every bridgeless simple graph with minimum degree at least three has a spanning even subgraph in which every component has at least four vertices. We deduce that if G is a simple bridgeless graph with n vertices and minimum degree at least three, then its line graph has a 2-factor with at most max{1,(3n-4)/10} components. This upper bound is best possible.