Skip to main content
Article
Spanning closed trails in graphs
Discrete Mathematics (1993)
  • Zhi-Hong Chen
Abstract
Let G be a 2-edge-connected simple graph on n>;95 vertices. Let l be the number of vertices of degree 2 in G. We prove that if l<n⧸5−19 and if, for every edge uvϵE(G),d(v)+d(v)⩾2n⧸5−2, then exactly one of the following holds: (a) G has a spanning closed trail; (b) G can be contracted to K2, c−2, where cmax{5, 3+l} is an odd number.
An example shows that if a graph satisfies the conditions above except that it has too many vertices of degree 2, then the conclusion fails. This result is related to a conjecture of Benhocine et al. (1986), recently proved by Veldman. We obtain some other related results.
Disciplines
Publication Date
July, 1993
DOI
https://doi.org/10.1016/0012-365X(93)90324-M
Publisher Statement
Note: full-text not available due to publisher restrictions. Link takes you to an external site where you can purchase the article or borrow it from a local library.
Citation Information
Zhi-Hong Chen. "Spanning closed trails in graphs" Discrete Mathematics Vol. 117 Iss. 1-3 (1993) p. 57 - 71 ISSN: 0012-365X
Available at: http://works.bepress.com/zhi_hong_chen/40/