{
  "id": "2308.13874",
  "version": "v1",
  "published": "2023-08-26T13:17:25.000Z",
  "updated": "2023-08-26T13:17:25.000Z",
  "title": "Sufficient conditions for $k$-factors and spanning trees of graphs",
  "authors": [
    "Guoyan Ao",
    "Ruifang Liu",
    "Jinjiang Yuan",
    "C. T. Ng",
    "T. C. E. Cheng"
  ],
  "comment": "17 pages, 3 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "For any integer $k\\geq1,$ a graph $G$ has a $k$-factor if it contains a $k$-regular spanning subgraph. In this paper we prove a sufficient condition in terms of the number of $r$-cliques to guarantee the existence of a $k$-factor in a graph with minimum degree at least $\\delta$, which improves the sufficient condition of O \\cite{O2021} based on the number of edges. For any integer $k\\geq2,$ a spanning $k$-tree of a connected graph $G$ is a spanning tree in which every vertex has degree at most $k$. Motivated by the technique of Li and Ning \\cite{Li2016}, we present a tight spectral condition for an $m$-connected graph to have a spanning $k$-tree, which extends the result of Fan, Goryainov, Huang and Lin \\cite{Fan2021} from $m=1$ to general $m$. Let $T$ be a spanning tree of a connected graph. The leaf degree of $T$ is the maximum number of leaves adjacent to $v$ in $T$ for any $v\\in V(T)$. We provide a tight spectral condition for the existence of a spanning tree with leaf degree at most $k$ in a connected graph with minimum degree $\\delta$, where $k\\geq1$ is an integer.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-08-26T13:17:25.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C50",
      "05C35"
    ],
    "keywords": [
      "spanning tree",
      "sufficient condition",
      "connected graph",
      "tight spectral condition",
      "minimum degree"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}