DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

W. Zheng, H. Broersma, L. Wang

Title:

Toughness, forbidden subgraphs, and<br> Hamilton-connected graphs

Source:

Discussiones Mathematicae Graph Theory

Received: 2019-05-27, Revised: 2019-08-30, Accepted: 2019-08-30, https://doi.org/10.7151/dmgt.2247

Abstract:

A graph $G$ is called Hamilton-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\cdot \omega(G-X) \leq |X|$ for all $X\subseteq V(G)$ with $\omega(G-X)>1$. The toughness of $G$, denoted $\tau(G)$, is the maximum value of $t$ such that $G$ is $t$-tough (taking $\tau(K_n)=\infty$ for all $n\geq1$). It is known that a Hamilton-connected graph $G$ has toughness $\tau(G)>1$, but that the reverse statement does not hold in general. In this paper, we investigate all possible forbidden subgraphs $H$ such that every $H$-free graph $G$ with $\tau(G)>1$ is Hamilton-connected. We find that the results are completely analogous to the {Hamiltonian} case: every graph $H$ such that any 1-tough $H$-free graph is {Hamiltonian} also ensures that every $H$-free graph with toughness larger than one is Hamilton-connected. And similarly, there is no other forbidden subgraph having this property, except possibly for the graph $K_1\cup P_4$ itself. We leave this as an open case.

Keywords:

toughness, forbidden subgraph, Hamilton-connected graph, Hamiltonicity

PDF
Close