Spanning 2-trails from degree sum conditions
✍ Scribed by M. N. Ellingham; Xiaoya Zha; Yi Zhang
- Publisher
- John Wiley and Sons
- Year
- 2004
- Tongue
- English
- Weight
- 199 KB
- Volume
- 45
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
Suppose G is a simple connected n‐vertex graph. Let σ~3~(G) denote the minimum degree sum of three independent vertices in G (which is ∞ if G has no set of three independent vertices). A 2‐trail is a trail that uses every vertex at most twice. Spanning 2‐trails generalize hamilton paths and cycles. We prove three main results. First, if σ~3~G)≥ n ‐ 1, then G has a spanning 2‐trail, unless G ≅ K~1,3~. Second, if σ~3~(G) ≥ n, then G has either a hamilton path or a closed spanning 2‐trail. Third, if G is 2‐edge‐connected and σ~3~(G) ≥ n, then G has a closed spanning 2‐trail, unless G ≅ K~2,3~ or K (the 6‐vertex graph obtained from K~2,3~ by subdividing one edge). All three results are sharp. These results are related to the study of connected and 2‐edge‐connected factors, spanning k‐walks, even factors, and supereulerian graphs. In particular, a closed spanning 2‐trail may be regarded as a connected (and 2‐edge‐connected) even [2,4]‐factor. © 2004 Wiley Periodicals, Inc. J Graph Theory 45: 298–319, 2004