{
  "id": "2408.01475",
  "version": "v1",
  "published": "2024-08-02T06:42:23.000Z",
  "updated": "2024-08-02T06:42:23.000Z",
  "title": "Ramsey theory and strength of graphs",
  "authors": [
    "Rikio Ichishima",
    "Francesc A Muntaner-Batle",
    "Yukio Takahashi"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "A numbering $f$ of a graph $G$ of order $n$ is a labeling that assigns distinct elements of the set $\\left\\{ 1,2,\\ldots ,n\\right\\} $ to the vertices of $G$, where each $uv\\in E\\left( G\\right) $ is labeled $f\\left( u\\right) +f\\left( v\\right) $. The strength $\\mathrm{str}\\left( G\\right) $ of $G$ is defined by $\\mathrm{str}\\left( G\\right) =\\min \\left\\{ \\mathrm{str}_{f}\\left( G\\right) \\left\\vert f\\text{ is a numbering of }G\\right. \\right\\}$, where $\\mathrm{str}_{f}\\left( G\\right) =\\max \\left\\{ f\\left( u\\right) +f\\left( v\\right) \\left\\vert uv\\in E\\left( G\\right) \\right. \\right\\} $. Let $f\\left( n\\right) $ denote the maximum of $\\mathrm{str}\\left( G\\right) +% \\mathrm{str}\\left( \\overline{G}\\right) $ over nonempty graphs $G$ and $% \\overline{G}$ of order $n$, where $\\overline{G}$ represents the complement of $G$. In this paper, we establish a lower bound for the Ramsey numbers related to the concept of strength of a graph and show a sharp lower bound for $f\\left( n\\right) $. In addition to these results, we provide another lower bound and remark some exact values for $f\\left( n\\right) $. Furthermore, we extend existing necessary and sufficient conditions involving the strength of a graph. Finally, we investigate bounds for $\\mathrm{str}\\left( G\\right) +\\mathrm{str}\\left( \\overline{G}\\right) $ whenever $G$ and $\\overline{G}$ are nonempty graphs of order $n$. Throughout this paper, we propose some open problems arising from our study.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-08-02T06:42:23.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "ramsey theory",
      "nonempty graphs",
      "assigns distinct elements",
      "sharp lower bound",
      "exact values"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}