{
  "id": "1301.1157",
  "version": "v1",
  "published": "2013-01-07T11:41:18.000Z",
  "updated": "2013-01-07T11:41:18.000Z",
  "title": "Determination of the prime bound of a graph",
  "authors": [
    "Abderrahim Boussaïri",
    "Pierre Ille"
  ],
  "comment": "arXiv admin note: text overlap with arXiv:1110.2935",
  "categories": [
    "math.CO"
  ],
  "abstract": "Given a graph $G$, a subset $M$ of $V(G)$ is a module of $G$ if for each $v\\in V(G)\\setminus M$, $v$ is adjacent to all the elements of $M$ or to none of them. For instance, $V(G)$, $\\emptyset$ and $\\{v\\}$ ($v\\in V(G)$) are modules of $G$ called trivial. Given a graph $G$, $\\omega_M(G)$ (respectively $\\alpha_M(G)$) denotes the largest integer $m$ such that there is a module $M$ of $G$ which is a clique (respectively a stable) set in $G$ with $|M|=m$. A graph $G$ is prime if $|V(G)|\\geq 4$ and if all its modules are trivial. The prime bound of $G$ is the smallest integer $p(G)$ such that there is a prime graph $H$ with $V(H)\\supseteq V(G)$, $H[V(G)]=G$ and $|V(H)\\setminus V(G)|=p(G)$. We establish the following. For every graph $G$ such that $\\max(\\alpha_M(G),\\omega_M(G))\\geq 2$ and $\\log_2(\\max(\\alpha_M(G),\\omega_M(G)))$ is not an integer, $p(G)=\\lceil\\log_2(\\max(\\alpha_M(G),\\omega_M(G)))\\rceil$. Then, we prove that for every graph $G$ such that $\\max(\\alpha_M(G),\\omega_M(G))=2^k$ where $k\\geq 1$, $p(G)=k$ or $k+1$. Moreover $p(G)=k+1$ if and only if $G$ or its complement admits $2^k$ isolated vertices. Lastly, we show that $p(G)=1$ for every non prime graph $G$ such that $|V(G)|\\geq 4$ and $\\alpha_M(G)=\\omega_M(G)=1$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-01-07T11:41:18.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C70",
      "05C69"
    ],
    "keywords": [
      "prime bound",
      "determination",
      "non prime graph",
      "smallest integer",
      "complement admits"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1301.1157B"
    }
  }
}