Critical and Maximum Independent Sets of a Graph

2015/05/31 by Jarden, Adi, Levit, Vadim E., Mandrescu, Eugen
#05C69 (Primary) 05C70 (Secondary) #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2

paper · doi:10.48550/arxiv.1506.00255

Abstract

Let G be a simple graph with vertex set V(G). A subset S of V(G) is independent if no two vertices from S are adjacent. By Ind(G) we mean the family of all independent sets of G while core(G) and corona(G) denote the intersection and the union of all maximum independent sets, respectively. The number d(X)= |X|-|N(X)| is the difference of the set of vertices X, and an independent set A is critical if d(A)=maxd(I):I belongs to Ind(G) (Zhang, 1990). Let ker(G) and diadem(G) be the intersection and union, respectively, of all critical independent sets of G (Levit and Mandrescu, 2012). In this paper, we present various connections between critical unions and intersections of maximum independent sets of a graph. These relations give birth to new characterizations of Koenig-Egervary graphs, some of them involving ker(G), core(G), corona(G), and diadem(G).

Related

• Critical Independent Sets of a Graph
• On some conjectures concerning critical independent sets of a graph
• On Konig-Egervary Collections of Maximum Critical Independent Sets
• On the Structure of the Minimum Critical Independent Set of a Graph
• On the Intersection of All Critical Sets of a Unicyclic Graph