Spanning closed trails in graphs

✍ Scribed by Zhi-Hong Chen

• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 708 KB
• Volume: 117
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(93)90324-m

✦ Synopsis

Let G be a 2-edge-connected simple graph on n > 95 vertices. Let 1 be the number of vertices of degree 2 in G. We prove that if I < n/5 -19 and if, for every edge uveE(G), d(u) + 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 K,,,_,, where c < max { 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 recently proved by Veldman. We obtain some other related results.

Theorem 1.1 (Veldman [lo]). Zf G is a connected simple graph of order n such that G-D 1 (G) is 2-edge-connected and, for every edge uv of G, d(u) + d(v) > 2n/5 -2, then, for n sufJiciently large, G has a closed trail containing at least one end of every edge of G.