Critical Sets in Bipartite Graphs

Details Critical Sets in Bipartite Graphs Critical Sets in Bipartite Graphs

2011-02-06

arxiv.org/abs/1102.1138v2

Computer Science

Discrete Mathematics

13 pages, 8 figures

Scientific paper

Let G=(V,E) be a graph. A set S is independent if no two vertices from S are adjacent, alpha(G) is the size of a maximum independent set, and core(G) is the intersection of all maximum independent sets. The number d(X)=|X|-|N(X)| is the difference of the set X, and d_{c}(G)=max{d(I):I is an independent set} is called the critical difference of G. A set X is critical if d(X)=d_{c}(G). For a graph G we define ker(G) as the intersection of all critical independent sets, while diadem(G) is the union of all critical independent sets. For a bipartite graph G=(A,B,E), with bipartition {A,B}, Ore defined delta(X)=d(X) for every subset X of A, while delta_0(A)=max{delta(X):X is a subset of A}. Similarly is defined delta_0(B). In this paper we prove that for every bipartite graph G=(A,B,E) the following assertions hold: d_{c}(G)=delta_0(A)+delta_0(B); ker(G)=core(G); |ker(G)|+|diadem(G)|=2*alpha(G).

Affiliated with

Also associated with

No associations

Rating

Critical Sets in Bipartite Graphs 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 Critical Sets in Bipartite Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Critical Sets in Bipartite Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-506029