摘要
A graph G is called hamiltonian-connected if for every pair of distinct vertices {u, v} of G there exists a Hamilton path in G that connects u and v. A graph G is said to be t-tough if t•w(G-X)≥ |X| for all X ≤ V (G) with (G-X) > 1. The toughness of G, denoted (G), is the maximum value of t such that G is t-tough (taking (Kn) = 1 for all n ≤ 1). It is known that a hamiltonian-connected graph G has toughness τ (G) > 1, but that the reverse statement does not hold in general. In this presentation, we investigate all possible forbidden subgraphs H such that every H-free graph G with τ(G) > 1 is hamiltonian-connected. Except for one open case H = K1 [ P4, we characterize all possible graphs H with this property.
源语言 | 英语 |
---|---|
页 | 139-142 |
页数 | 4 |
出版状态 | 已出版 - 2019 |
活动 | 17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2019 - Enschede, 荷兰 期限: 1 7月 2019 → 3 7月 2019 |
会议
会议 | 17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2019 |
---|---|
国家/地区 | 荷兰 |
市 | Enschede |
时期 | 1/07/19 → 3/07/19 |