On dominating and spanning circuits in graphs


Veldman, H.J. (1994) On dominating and spanning circuits in graphs. Discrete Mathematics, 124 (1-3). pp. 229-239. ISSN 0012-365X

Abstract:An eulerian subgraph of a graph is called a circuit. As shown by Harary and Nash-Williams, 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 degree-sums 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/5n-1) 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/0012-365X(92)00063-W
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 140378