Toughness and forbidden subgraphs for hamiltonian-connected graphs

Wei Zheng, Hajo Broersma, Ligong Wang

科研成果: 会议稿件论文同行评审

摘要

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月 20193 7月 2019

会议

会议17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2019
国家/地区荷兰
Enschede
时期1/07/193/07/19

指纹

探究 'Toughness and forbidden subgraphs for hamiltonian-connected graphs' 的科研主题。它们共同构成独一无二的指纹。

引用此