Prime bound of a graph

Abderrahim Boussaïri, Pierre Ille

Published 2011-10-13Version 1

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.