{
  "id": "2304.00859",
  "version": "v1",
  "published": "2023-04-03T10:14:37.000Z",
  "updated": "2023-04-03T10:14:37.000Z",
  "title": "On the strength and domination number of graphs",
  "authors": [
    "Yukio Takahashi",
    "Rikio Ichishima",
    "Francesc A. Muntaner-Batle"
  ],
  "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$. The strength $\\textrm{str}_{f}\\left( G\\right)$ of a numbering $f:V\\left( G\\right) \\rightarrow \\left\\{ 1,2,\\ldots ,n\\right\\} $ of $G$ is defined by% \\begin{equation*} \\mathrm{str}_{f}\\left( G\\right) =\\max \\left\\{ f\\left( u\\right) +f\\left( v\\right) \\left| uv\\in E\\left( G\\right) \\right. \\right\\} \\text{,} \\end{equation*}% that is, $\\mathrm{str}_{f}\\left( G\\right) $ is the maximum edge label of $G$ and the strength\\ \\textrm{str}$\\left( G\\right) $ of a graph $G$ itself is \\begin{equation*} \\mathrm{str}\\left( G\\right) =\\min \\left\\{ \\mathrm{str}_{f}\\left( G\\right) \\left| f\\text{ is a numbering of }G\\right. \\right\\} \\text{.} \\end{equation*} In this paper, we present a sharp lower bound for the strength of a graph in terms of its domination number as well as its (edge) covering and (edge) independence number. We also provide a necessary and sufficient condition for the strength of a graph to attain the earlier bound in terms of their subgraph structure. In addition, we establish a sharp lower bound for the domination number of a graph under certain conditions.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-04-03T10:14:37.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C78",
      "90C27"
    ],
    "keywords": [
      "domination number",
      "sharp lower bound",
      "maximum edge label",
      "assigns distinct elements",
      "independence number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}