Premium
Spanning 2‐trails from degree sum conditions
Author(s) -
Ellingham M. N.,
Zha Xiaoya,
Zhang Yi
Publication year - 2004
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10162
Subject(s) - combinatorics , mathematics , vertex (graph theory) , connectivity , graph , simple graph , spanning tree , bound graph , degree (music) , discrete mathematics , graph power , line graph , physics , acoustics
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