On circuits and pancyclic line graphs

✍ Scribed by A. Benhocine; L. Clark; N. Köhler; H. J. Veldman

• Publisher: John Wiley and Sons
• Year: 1986
• Tongue: English
• Weight: 649 KB
• Volume: 10
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190100317

✦ Synopsis

Clark proved that L(G) is hamiltonian if G is a connected graph of order n 2 6 such that deg u + deg v 2 n -1p(n) for every edge uv of G, where p(n) = 0 if n is even and p(n) = 1 if n is odd. Here it is shown that the bound n -1 -dn) can be decreased to (2n + 1)/3 if every bridge of G is incident with a vertex of degree 1, which is a necessary condition for hamiltonicity of L(G). Moreover, the conclusion that L(G) is hamiltonian can be strengthened to the conclusion that L ( G ) is pancyclic. Lesniak-Foster and Williamson proved that G contains a spanning closed trail if IV(G)J = n 2 6, 6 ( G ) 2 2 and deg u + deg v 2 n -1 for every pair of nonadjacent vertices u and v. The bound n -1 can be decreased to (2n + 3)/3 if G is connected and bridgeless, which is necessary for G to have a spanning closed trail.

1. TERMINOLOGY

We use 141 for basic terminology and notation, but speak of vertices and edges instead of points and lines. Accordingly we denote the edge set of a graph G by E(G). In [7] a circuit was defined as a nontrivial closed trail. Here the following subtle variation on this definition will be more convenient. A circuit C of a graph G is a nontrivial eulerian subgraph of G. Alternatively, C is a circuit if