Spanning trails with variations of Chvátal-Erdős conditions

详细信息    查看全文

• 作者：Zhi-Hong Chen^a ; ^{chen@butler.edu} ; Hong-Jian Lai^b ; ^{hong-jian.lai@mail.wvu.edu} ; Meng Zhang^c ; ^{meng.zhang@ung.edu}
• 关键词：Spanning trail ; Supereulerian ; Collapsible ; Independence number ; Matching number
• 刊名：Discrete Mathematics
• 出版年：2017
• 出版时间：6 February 2017
• 年：2017
• 卷：340
• 期：2
• 页码：243-251
• 全文大小：488 K
• 卷排序：340

文摘

Let α(G)α(G), α′(G)α′(G), κ(G)κ(G) and κ′(G)κ′(G) denote the independence number, the matching number, connectivity and edge connectivity of a graph GG, respectively. We determine the finite graph families F1F1 and F2F2 such that each of the following holds.(i) If a connected graph GG satisfies κ′(G)≥α(G)−1κ′(G)≥α(G)−1, then GG has a spanning closed trail if and only if GG is not contractible to a member of F1F1.(ii) If κ′(G)≥max{2,α(G)−3}κ′(G)≥max{2,α(G)−3}, then GG has a spanning trail. This result is best possible.(iii) If a connected graph GG satisfies κ′(G)≥3κ′(G)≥3 and α′(G)≤7α′(G)≤7, then GG has a spanning closed trail if and only if GG is not contractible to a member of F2F2.