Prime bound of a graph

Details Prime bound of a graph Prime bound of a graph

2011-10-13

arxiv.org/abs/1110.2935v1

Mathematics

Combinatorics

22 pages, 3 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Prime bound of a graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Prime bound of a graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Prime bound of a graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-500299