Article
Spanning trails with variations of Chvátal–Erdős conditions
Discrete Mathematics
(2017)
Abstract
Let α(G), α′(G), κ(G) and κ′(G) denote the independence number, the matching number, connectivity and edge connectivity of a graph G, respectively. We determine the finite graph families F1 and F2 such that each of the following holds.
(i) If a connected graph G satisfies κ′(G)≥α(G)−1, then G has a spanning closed trail if and only if G is not contractible to a member of F1.
(ii) If κ′(G)≥max{2,α(G)−3}, then G has a spanning trail. This result is best possible.
(iii) If a connected graph G satisfies κ′(G)≥3 and α′(G)≤7, then G has a spanning closed trail if and only if G is not contractible to a member of F2.
Keywords
- Spanning trail,
- Supereulerian,
- Collapsible,
- Independence number,
- Matching number
Disciplines
Publication Date
February, 2017
DOI
https://doi.org/10.1016/j.disc.2016.08.002
Publisher Statement
Note: full-text not available due to publisher restrictions. Link takes you to an external site where you can purchase the article or borrow it from a local library.
Citation Information
Zhi-Hong Chen, Hong-Jian Lai and Meng Zhang. "Spanning trails with variations of Chvátal–Erdős conditions" Discrete Mathematics Vol. 340 Iss. 2 (2017) p. 243 - 251 ISSN: 0012-365X Available at: http://works.bepress.com/zhi_hong_chen/17/