DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

W. Zheng

Wei Zheng

University of Twente

email: w.zheng@utwente.nl

H.J. Broersma

Hajo Broersma

Department of Applied MathematicsFaculty EEMCSUniversity of TwenteP.O. Box 2177500 AE ENSCHEDETHE NETHERLANDS

email: h.j.broersma@utwente.nl

0000-0002-4678-3210

L. Wang

Title:

Toughness, forbidden subgraphs, and Hamiltonian-connected graphs

PDF

Source:

Discussiones Mathematicae Graph Theory 42(1) (2022) 187-196

Received: 2019-05-27 , Revised: 2019-08-30 , Accepted: 2019-08-30 , Available online: 2019-11-02 , 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, Hamiltonian-connected graph, Hamiltonicity

References:

  1. D. Bauer, H.J. Broersma, J.P.M. van den Heuvel and H.J. Veldman, On Hamiltonian properties of $2$-tough graphs, J. Graph Theory 18 (1994) 539–543.
    https://doi.org/10.1002/jgt.3190180602
  2. D. Bauer, H.J. Broersma and H.J. Veldman, Not every $2$-tough graph is Hamiltonian, Discrete Appl. Math. 99 (2000) 317–321.
    https://doi.org/10.1016/S0166-218X(99)00141-9
  3. D. Bauer, H.J. Broersma and E. Schmeichel, Toughness in graphs–-A survey, Graphs Combin. 22 (2006) 1–35.
    https://doi.org/10.1007/s00373-006-0649-0
  4. J.A. Bondy and U.S.R. Murty, Graph Theory (Grad. Texts in Math. 244 Springer-Verlag, London, 2008).
  5. H.J. Broersma, How tough is toughness$?$, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 117 (2015).
  6. G. Chen and R.J. Gould, Hamiltonian connected graphs involving forbidden subgraphs, Bull. Inst. Combin. Appl. 29 (2000) 25–32.
  7. V. Chvátal, Tough graphs and Hamiltonian circuits, Discrete Math. 5 (1973) 215–228.
    https://doi.org/10.1016/0012-365X(73)90138-6
  8. H.A. Jung, On a class of posets and the corresponding comparability graphs, J. Combin. Theory Ser. B 24 (1978) 125–133.
    https://doi.org/10.1016/0095-8956(78)90013-8
  9. D. Kratsch, J. Lehel and H. Müller, Toughness, Hamiltonicity and split graphs, Discrete Math. 150 (1996) 231–245.
    https://doi.org/10.1016/0012-365X(95)00190-8
  10. B. Li, H.J. Broersma and S. Zhang, Forbidden subgraphs for Hamiltonicity of $1$-tough graphs, Discuss. Math. Graph Theory 36 (2016) 915–929.
    https://doi.org/10.7151/dmgt.1897
  11. M.M. Matthews and D.P. Sumner, Hamiltonian results in $K_{1,3}$-free graphs, J. Graph Theory 8 (1984) 139–146.
    https://doi.org/10.1002/jgt.3190080116
  12. Zh.G. Nikoghosyan, Disconnected forbidden subgraphs, toughness and Hamilton cycles, ISRN Combinatorics 2013 (2013) 673971.
    https://doi.org/10.1155/2013/673971
Close