On hamiltonian cycles of 1-tough $(P_{2} \cup kP_{1})$-free graphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914579590676480 |
|---|---|
| author | Sanka, Masahiro |
| author_facet | Sanka, Masahiro |
| contents | Let $k$ be a positive integer. A graph is said to be $(P_2 \cup kP_1)$-free if it does not contain $P_2 \cup kP_1$ as an induced subgraph. Recently, Ota and the author asked whether every 1-tough and $k$-connected $(P_2 \cup kP_1)$-free graph is hamiltonian or the Petersen graph. Note that this problem is affirmative for $k \in \{1,2,3\}$ by the known results. In this paper, we show that for each integer $k \geq 4$, if $G$ is a $1$-tough and $(k-1)$-connected $(P_2 \cup kP_1)$-free graph with $|V(G)| \ge k^2+k+1$ and $δ(G) \ge k$, then $G$ is hamiltonian. This result implies that the above question is affirmative for large graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_19508 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On hamiltonian cycles of 1-tough $(P_{2} \cup kP_{1})$-free graphs Sanka, Masahiro Combinatorics 05C45 Let $k$ be a positive integer. A graph is said to be $(P_2 \cup kP_1)$-free if it does not contain $P_2 \cup kP_1$ as an induced subgraph. Recently, Ota and the author asked whether every 1-tough and $k$-connected $(P_2 \cup kP_1)$-free graph is hamiltonian or the Petersen graph. Note that this problem is affirmative for $k \in \{1,2,3\}$ by the known results. In this paper, we show that for each integer $k \geq 4$, if $G$ is a $1$-tough and $(k-1)$-connected $(P_2 \cup kP_1)$-free graph with $|V(G)| \ge k^2+k+1$ and $δ(G) \ge k$, then $G$ is hamiltonian. This result implies that the above question is affirmative for large graphs. |
| title | On hamiltonian cycles of 1-tough $(P_{2} \cup kP_{1})$-free graphs |
| topic | Combinatorics 05C45 |
| url | https://arxiv.org/abs/2605.19508 |