{
  "id": "2212.14060",
  "version": "v1",
  "published": "2022-12-28T19:01:13.000Z",
  "updated": "2022-12-28T19:01:13.000Z",
  "title": "The optimal bound on the 3-independence number obtainable from a polynomial-type method",
  "authors": [
    "Lord C. Kavi",
    "Michael W. Newman"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "A $k$-independent set in a connected graph is a set of vertices such that any two vertices in the set are at distance greater than $k$ in the graph. The $k$-independence number of a graph, denoted $\\alpha_k$, is the size of a largest $k$-independent set in the graph. Recent results have made use of polynomials that depend on the spectrum of the graph to bound the $k$-independence number. They are optimized for the cases $k=1,2$. There are polynomials that give good (and sometimes) optimal results for general $k$, including case $k=3$. In this paper, we provide the best possible bound that can be obtained by choosing a polynomial for case $k=3$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-12-28T19:01:13.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C50",
      "05C69"
    ],
    "keywords": [
      "optimal bound",
      "polynomial-type method",
      "number obtainable",
      "independence number",
      "independent set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}