On dominating and spanning circuits in graphs
Veldman, H.J. (1994) On dominating and spanning circuits in graphs. Discrete Mathematics, 124 (13). pp. 229239. ISSN 0012365X

PDF
696kB 
Abstract:  An eulerian subgraph of a graph is called a circuit. As shown by Harary and NashWilliams, the existence of a Hamilton cycle in the line graph L(G) of a graph G is equivalent to the existence of a dominating circuit in G, i.e., a circuit such that every edge of G is incident with a vertex of the circuit. Important progress in the study of the existence of spanning and dominating circuits was made by Catlin, who defined the reduction of a graph G and showed that G has a spanning circuit if and only if the reduction of G has a spanning circuit. We refine Catlin's reduction technique to obtain a result which contains several known and new sufficient conditions for a graph to have a spanning or dominating circuit in terms of degreesums of adjacent vertices. In particular, the result implies the truth of the following conjecture of Benhocine et al.: If G is a connected simple graph of order n such that every cut edge of G is incident with a vertex of degree 1 and d(u)+d(v) > 2(1/5n1) for every edge uv of G, then, for n sufficiently large, L(G) is hamiltonian. 
Item Type:  Article 
Copyright:  © 1994 Elsevier Science 
Link to this item:  http://purl.utwente.nl/publications/29744 
Official URL:  http://dx.doi.org/10.1016/0012365X(92)00063W 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page
Metis ID: 140378