Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs
A graph G is said to be 1-tough if for every vertex cut S of G, the number of components of G − S does not exceed |S|. Being 1-tough is an obvious necessary condition for a graph to be hamiltonian, but it is not sufficient in general. We study the problem of characterizing all graphs H such that eve...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2016-11-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.1897 |
| _version_ | 1797718042848788480 |
|---|---|
| author | Li Binlong Broersma Hajo J. Zhang Shenggui |
| author_facet | Li Binlong Broersma Hajo J. Zhang Shenggui |
| author_sort | Li Binlong |
| collection | DOAJ |
| description | A graph G is said to be 1-tough if for every vertex cut S of G, the number of components of G − S does not exceed |S|. Being 1-tough is an obvious necessary condition for a graph to be hamiltonian, but it is not sufficient in general. We study the problem of characterizing all graphs H such that every 1-tough H-free graph is hamiltonian. We almost obtain a complete solution to this problem, leaving H = K1 ∪ P4 as the only open case. |
| first_indexed | 2024-03-12T08:45:14Z |
| format | Article |
| id | doaj.art-d0375a48f0474f1fb97fb44a55e46d6d |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T08:45:14Z |
| publishDate | 2016-11-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-d0375a48f0474f1fb97fb44a55e46d6d2023-09-02T16:29:57ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922016-11-0136491592910.7151/dmgt.1897dmgt.1897Forbidden Subgraphs for Hamiltonicity of 1-Tough GraphsLi Binlong0Broersma Hajo J.1Zhang Shenggui2Department of Applied Mathematics, School of Science, Northwestern Polytechnical University, Xi’an, Shaanxi 710072, P.R. ChinaFaculty of EEMCS, University of Twente 7500 AE Enschede, NetherlandsDepartment of Applied Mathematics, School of Science Northwestern Polytechnical University Xi’an, Shaanxi 710072, P.R., ChinaA graph G is said to be 1-tough if for every vertex cut S of G, the number of components of G − S does not exceed |S|. Being 1-tough is an obvious necessary condition for a graph to be hamiltonian, but it is not sufficient in general. We study the problem of characterizing all graphs H such that every 1-tough H-free graph is hamiltonian. We almost obtain a complete solution to this problem, leaving H = K1 ∪ P4 as the only open case.https://doi.org/10.7151/dmgt.1897forbidden subgraph1-tough graphh-free graphhamiltonian graph |
| spellingShingle | Li Binlong Broersma Hajo J. Zhang Shenggui Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs Discussiones Mathematicae Graph Theory forbidden subgraph 1-tough graph h-free graph hamiltonian graph |
| title | Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs |
| title_full | Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs |
| title_fullStr | Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs |
| title_full_unstemmed | Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs |
| title_short | Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs |
| title_sort | forbidden subgraphs for hamiltonicity of 1 tough graphs |
| topic | forbidden subgraph 1-tough graph h-free graph hamiltonian graph |
| url | https://doi.org/10.7151/dmgt.1897 |
| work_keys_str_mv | AT libinlong forbiddensubgraphsforhamiltonicityof1toughgraphs AT broersmahajoj forbiddensubgraphsforhamiltonicityof1toughgraphs AT zhangshenggui forbiddensubgraphsforhamiltonicityof1toughgraphs |