Spanning Trails with Maximum Degree at Most 4 in -Free Graphs

作者：Chen Guantao; Ellingham M N; Saito Akira; Shan Songling^*

来源：Graphs and Combinatorics, 2017, 33(5): 1095-1101.

DOI：10.1007/s00373-017-1823-2

• Toughness
• 2K2-free graph
• 2-trail
• Dominating cycle

A graph is called -free if it does not contain two independent edges as an induced subgraph. Gao and Pasechnik conjectured that every -tough -free graph with at least three vertices has a spanning trail with maximum degree at most 4. In this paper, we confirm this conjecture. We also provide examples for all of t-tough graphs that do not have a spanning trail with maximum degree at most 4.

• 出版日期2017-9