Spanning 2‐trails from degree sum conditions

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   * 2,3(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