×

On dominating and spanning circuits in graphs. (English) Zbl 0789.05061

Summary: 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 \over 5} n-1)\) for every edge \(uv\) of \(G\), then, for \(n\) sufficiently large, \(L(G)\) is hamiltonian.

MSC:

05C45 Eulerian and Hamiltonian graphs
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Benhocine, A.; Clark, L.; Köhler, N.; Veldman, H. J., On circuits and pancyclic line graphs, J. Graph Theory, 10, 411-425 (1986) · Zbl 0608.05056
[2] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), Macmillan: Macmillan London, Elsevier, Amsterdam · Zbl 1134.05001
[3] Catlin, P. A., A reduction method to find spanning eulerian subgraphs, J. Graph Theory, 12, 29-44 (1988) · Zbl 0659.05073
[4] Catlin, P. A., Contractions of graphs with no spanning eulerian subgraphs, Combinatorica, 8, 313-321 (1988) · Zbl 0659.05064
[5] Catlin, P. A., Spanning closed trails in graphs (1985), preprint
[6] Catlin, P. A., Spanning eulerian subgraphs and matchings, Discrete Math., 76, 95-116 (1989) · Zbl 0679.05051
[7] Catlin, P. A.; Li, X. W., Supereulerian graphs of minimum degree at least 4 (1989), preprint
[8] Chen, Z.-H., Supereulerian graphs and the Petersen graph, J. Combin. Math. Combin. Comput., 9, 79-89 (1991) · Zbl 0751.05065
[9] Chen, Z.-H.; Lai, H.-J., Collapsible graphs and matchings (1989), preprint
[10] Clark, L., On hamiltonian line graphs, J. Graph Theory, 8, 303-307 (1984) · Zbl 0535.05044
[11] Harary, F.; Nash-Williams, C. S.J. A., On eulerian and hamiltonian graphs and line graphs, Canad. Math. Bull., 8, 701-710 (1965) · Zbl 0136.44704
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.