{
  "id": "2407.19149",
  "version": "v1",
  "published": "2024-07-27T02:30:08.000Z",
  "updated": "2024-07-27T02:30:08.000Z",
  "title": "A Fan-type condition for cycles in $1$-tough and $k$-connected $(P_2\\cup kP_1)$-free graphs",
  "authors": [
    "Zhiquan Hu",
    "Jie Wang",
    "Changlong Shen"
  ],
  "comment": "19 pages, 4 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-07-27T02:30:08.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C38",
      "05C45",
      "G.2.2"
    ],
    "keywords": [
      "free graph",
      "fan-type condition",
      "independent sets",
      "fan-type theorem",
      "hamiltonian"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 19,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}