Determination of the prime bound of a graph

zbMATH Open1317.05135arXiv1301.1157MaRDI QIDQ5499957

Abderrahim Boussaïri, Pierre Ille

Publication date: 5 August 2015

Abstract: Given a graph $G$, a subset $M$ of $V(G)$ is a module of $G$ if for each $vinV(G)setminusM$, $v$ is adjacent to all the elements of $M$ or to none of them. For instance, $V(G)$, $emptyset$ and $v$ ($vinV(G)$) are modules of $G$ called trivial. Given a graph $G$, $omeg{a}_M(G)$ (respectively $alph{a}_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)|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)setminusV(G)|=p(G)$. We establish the following. For every graph $G$ such that $max(alph{a}_M(G),omeg{a}_M(G))geq2$ and $lo{g}_2(max(alph{a}_M(G),omeg{a}_M(G)))$ is not an integer, $p(G)=lceillo{g}_2(max(alph{a}_M(G),omeg{a}_M(G)))ceil$. Then, we prove that for every graph $G$ such that $max(alph{a}_M(G),omeg{a}_M(G))=2^k$ where $kgeq1$, $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 $alph{a}_M(G)=omeg{a}_M(G)=1$.

Full work available at URL: https://arxiv.org/abs/1301.1157

zbMATH Keywords

moduleprime graphprime extensionmodular clique numbermodular stability numberprime bound

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (2)

Making a tournament indecomposable by one subtournament-reversal operation ⋮ Editing to prime graphs

This page was built for publication: Determination of the prime bound of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5499957)