{
  "id": "1110.2935",
  "version": "v1",
  "published": "2011-10-13T13:27:25.000Z",
  "updated": "2011-10-13T13:27:25.000Z",
  "title": "Prime bound of a graph",
  "authors": [
    "Abderrahim Boussaïri",
    "Pierre Ille"
  ],
  "comment": "22 pages, 3 figures",
  "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) \\diagdownM, v is adjacent to all the elements of M or to none of them. For instance, V(G), \\varnothing and {v} (v \\in V(G)) are modules of G called trivial. Given a graph G, m(G) denotes the largest integer m such that there is a module M of G which is a clique or a stable set in G with |M|=m. A graph G is prime if |V(G)|\\geq4 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)\\supseteqV(G), H[V(G)] = G and |V(H)\\diagdownV(G)|=p(G). We establish the following. For every graph G such that m(G)\\geq2 and log_2(m(G)) is not an integer, p(G)=\\lceil log_2(m(G)) \\rceil. Then, we prove that for every graph G such that m(G)=2^k where k\\geq1, 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)|\\geq4 and m(G)=1.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-10-13T13:27:25.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C70",
      "05C69"
    ],
    "keywords": [
      "prime bound",
      "non-prime graph",
      "largest integer",
      "smallest integer",
      "complement admits"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 22,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1110.2935B"
    }
  }
}