{
  "id": "1409.4116",
  "version": "v1",
  "published": "2014-09-14T23:22:09.000Z",
  "updated": "2014-09-14T23:22:09.000Z",
  "title": "On Domination Number and Distance in Graphs",
  "authors": [
    "Cong X. Kang"
  ],
  "comment": "5 pages, 2 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "A vertex set $S$ of a graph $G$ is a \\emph{dominating set} if each vertex of $G$ either belongs to $S$ or is adjacent to a vertex in $S$. The \\emph{domination number} $\\gamma(G)$ of $G$ is the minimum cardinality of $S$ as $S$ varies over all dominating sets of $G$. It is known that $\\gamma(G) \\ge \\frac{1}{3}(diam(G)+1)$, where $diam(G)$ denotes the diameter of $G$. Define $C_r$ as the largest constant such that $\\gamma(G) \\ge C_r \\sum_{1 \\le i < j \\le r}d(x_i, x_j)$ for any $r$ vertices of an arbitrary connected graph $G$; then $C_2=\\frac{1}{3}$ in this view. The main result of this paper is that $C_r=\\frac{1}{r(r-1)}$ for $r\\geq 3$. It immediately follows that $\\gamma(G)\\geq \\mu(G)=\\frac{1}{n(n-1)}W(G)$, where $\\mu(G)$ and $W(G)$ are respectively the average distance and the Wiener index of $G$ of order $n$. As an application of our main result, we prove a conjecture of DeLaVi\\~{n}a et al.\\;that $\\gamma(G)\\geq \\frac{1}{2}(ecc_G(B)+1)$, where $ecc_G(B)$ denotes the eccentricity of the boundary of an arbitrary connected graph $G$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-09-14T23:22:09.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69",
      "05C12"
    ],
    "keywords": [
      "domination number",
      "arbitrary connected graph",
      "main result",
      "vertex set",
      "largest constant"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 5,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1409.4116K"
    }
  }
}