تقرير
A Fan-type condition for cycles in $1$-tough and $k$-connected $(P_2\cup kP_1)$-free graphs
العنوان: | 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 |
سنة النشر: | 2024 |
المجموعة: | Mathematics |
مصطلحات موضوعية: | Mathematics - Combinatorics, 05C38, 05C45, G.2.2 |
الوصف: | For a graph $G$, let $\mu_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 $\mu_{k+1}(G)\geq\frac{7k-6}{5}$, then $G$ is hamiltonian or the Petersen graph. Comment: 19 pages, 4 figures |
نوع الوثيقة: | Working Paper |
URL الوصول: | http://arxiv.org/abs/2407.19149 |
رقم الأكسشن: | edsarx.2407.19149 |
قاعدة البيانات: | arXiv |
الوصف غير متاح. |