On dominating and spanning circuits in graphs

H.J. Veldman

    Research output: Contribution to journalArticleAcademicpeer-review

    39 Citations (Scopus)
    159 Downloads (Pure)


    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.
    Original languageEnglish
    Pages (from-to)229-239
    Number of pages11
    JournalDiscrete mathematics
    Issue number1-3
    Publication statusPublished - 1994


    • METIS-140378
    • IR-29744


    Dive into the research topics of 'On dominating and spanning circuits in graphs'. Together they form a unique fingerprint.

    Cite this