Determination of the prime bound of a graph

Authors

  • Abderrahim Boussairi
  • Pierre Ille

DOI:

https://doi.org/10.11575/cdm.v9i1.62101

Abstract

Given a graph G, a subset M of V(G) is a module of G if for each vV(G)M, v is adjacent to all the elements of M or adjacent to none of them. For instance, V(G), and {v} (vV(G)) are modules of G called trivial. Given a graph G, ωM(G) (respectively α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)|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)V(G), H[V(G)]=G and |V(H)V(G)|=p(G). We establish the following. For every graph G such that max(αM(G),ωM(G))2 and log2(max(αM(G),ωM(G))) is not an integer, p(G)=log2(max(αM(G),ωM(G))). Then, we prove that for every graph G such that max(αM(G),ωM(G))=2k where k1, p(G)=k or k+1. Moreover p(G)=k+1 if and only if G or its complement admits exactly 2k isolated vertices. Lastly, we show that p(G)=1 for every non prime graph G such that |V(G)|4 and αM(G)=ωM(G)=1.

Downloads

Published

2014-08-31

Issue

Section

Articles