Spanning 2‐trails from degree sum conditions

M. N. Ellingham, Xiaoya Zha, Yi ZhangJournal of Graph Theory 2004 · DOI

Abstract

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
BibTeX
@article{ellingham2004spanning,
  author = {M. N. Ellingham and Xiaoya Zha and Yi Zhang},
  title = {{Spanning 2‐trails from degree sum conditions}},
  journal = {Journal of Graph Theory},
  year = {2004},
  doi = {10.1002/jgt.10162},
}

Loading related content...

Figure