A Fan-type condition for cycles in $1$-tough and $k$-connected $(P_2\cup kP_1)$-free graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911969605320704 |
|---|---|
| author | Hu, Zhiquan Wang, Jie Shen, Changlong |
| author_facet | Hu, Zhiquan Wang, Jie Shen, Changlong |
| contents | For a graph $G$, let $μ_k(G):=\min~\{\max_{x\in S}d_G(x):~S\in \mathcal{S}_k\}$, where $\mathcal{S}_k$ is the set consisting of all independent sets $\{u_1,\ldots,u_k\}$ of $G$ such that some vertex, say $u_i$ ($1\leq i\leq k$), is at distance two from every other vertex in it. A graph $G$ is $1$-tough if for each cut set $S\subseteq V(G)$, $G-S$ has at most $|S|$ components. Recently, Shi and Shan \cite{Shi} conjectured that for each integer $k\geq 4$, being $2k$-connected is sufficient for $1$-tough $(P_2\cup kP_1)$-free graphs to be hamiltonian, which was confirmed by Xu et al. \cite{Xu} and Ota and Sanka \cite{Ota2}, respectively. In this article, we generalize the above results through the following Fan-type theorem: Let $k$ be an integer with $k\geq 2$ and let $G$ be a $1$-tough and $k$-connected $(P_2\cup kP_1)$-free graph with $μ_{k+1}(G)\geq\frac{7k-6}{5}$, then $G$ is hamiltonian or the Petersen graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_19149 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Fan-type condition for cycles in $1$-tough and $k$-connected $(P_2\cup kP_1)$-free graphs Hu, Zhiquan Wang, Jie Shen, Changlong Combinatorics 05C38, 05C45 G.2.2 For a graph $G$, let $μ_k(G):=\min~\{\max_{x\in S}d_G(x):~S\in \mathcal{S}_k\}$, where $\mathcal{S}_k$ is the set consisting of all independent sets $\{u_1,\ldots,u_k\}$ of $G$ such that some vertex, say $u_i$ ($1\leq i\leq k$), is at distance two from every other vertex in it. A graph $G$ is $1$-tough if for each cut set $S\subseteq V(G)$, $G-S$ has at most $|S|$ components. Recently, Shi and Shan \cite{Shi} conjectured that for each integer $k\geq 4$, being $2k$-connected is sufficient for $1$-tough $(P_2\cup kP_1)$-free graphs to be hamiltonian, which was confirmed by Xu et al. \cite{Xu} and Ota and Sanka \cite{Ota2}, respectively. In this article, we generalize the above results through the following Fan-type theorem: Let $k$ be an integer with $k\geq 2$ and let $G$ be a $1$-tough and $k$-connected $(P_2\cup kP_1)$-free graph with $μ_{k+1}(G)\geq\frac{7k-6}{5}$, then $G$ is hamiltonian or the Petersen graph. |
| title | A Fan-type condition for cycles in $1$-tough and $k$-connected $(P_2\cup kP_1)$-free graphs |
| topic | Combinatorics 05C38, 05C45 G.2.2 |
| url | https://arxiv.org/abs/2407.19149 |