Critical Sets in Bipartite Graphs

2011/02/06 by Vadim E. Levit, Levit, Vadim E., Eugen Mandrescu +1 · 1 citation
Computer Science · Mathematics · #05C69 #05C70 (Primary) 05A20(Secondary) #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #acm:05C69 #acm:05C70 #cs.DM #math.CO #msc:05C69 #msc:05C70

paper · pdf · doi:10.48550/arxiv.1102.1138

13 pages, 8 figures

arxiv created 2011/02/09 · arxiv updated 2011/02/10

Abstract

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)=maxd(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₀(A)=maxdelta(X):X is a subset of A. Similarly is defined delta₀(B). In this paper we prove that for every bipartite graph G=(A,B,E) the following assertions hold: d_c(G)=delta₀(A)+delta₀(B); ker(G)=core(G); |ker(G)|+|diadem(G)|=2*alpha(G).

Cited by

• Critical Independent Sets of a Graph

Related

• On the Structure of the Minimum Critical Independent Set of a Graph
• Vertices Belonging to All Critical Independent Sets of a Graph
• Critical Independent Sets of a Graph
• Critical and Maximum Independent Sets of a Graph
• On the Intersection of All Critical Sets of a Unicyclic Graph