Determination of the prime bound of a graph

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)$, $\varnothing$ 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)|\ge 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))\ge 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\ge 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)|\ge 4$ and ${\alpha }_M(G)={\omega }_M(G)=1$.

arXiv admin note: text overlap with arXiv:1110.2935