On the Structure of the Minimum Critical Independent Set of a Graph

Details On the Structure of the Minimum Critical Independent Set of a Graph On the Structure of the Minimum Critical Independent Set of a Graph

2011-02-09

arxiv.org/abs/1102.1859v1

Computer Science

Discrete Mathematics

8 pages, 3 figures

Scientific paper

Let G=(V,E). A set S is independent if no two vertices from S are adjacent. The number d(X)= |X|-|N(X)| is the difference of X, and an independent set A is critical if d(A) = max{d(I):I is an independent set}. Let us recall that ker(G) is the intersection of all critical independent sets, and core(G) is the intersection of all maximum independent sets. Recently, it was established that ker(G) is a subset of core(G) is true for every graph, while the corresponding equality holds for bipartite graphs. In this paper we present various structural properties of ker(G). The main finding claims that ker(G) is equal to the union of all inclusion minimal independent sets with positive difference.

Affiliated with

Also associated with

No associations

Rating

On the Structure of the Minimum Critical Independent Set 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 On the Structure of the Minimum Critical Independent Set of a Graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Structure of the Minimum Critical Independent Set of a Graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-650268