On some conjectures concerning critical independent sets of a graph

2015/09/16 by Short, Taylor
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1509.05057

Abstract

Let G be a simple graph with vertex set V(G). A set S⊆ V(G) is independent if no two vertices from S are adjacent. For X⊆ V(G), the difference of X is d(X) = |X|-|N(X)| and an independent set A is critical if d(A) = max \d(X): X⊆ V(G) is an independent set\ (possibly A=∅). Let nucleus(G) and diadem(G) be the intersection and union, respectively, of all maximum size critical independent sets in G. In this paper, we will give two new characterizations of König-Egerváry graphs involving nucleus(G) and diadem(G). We also prove a related lower bound for the independence number of a graph. This work answers several conjectures posed by Jarden, Levit, and Mandrescu.

Related

• Critical and Maximum Independent Sets of a Graph
• On Konig-Egervary Collections of Maximum Critical Independent Sets
• Critical Independent Sets of a Graph
• Critical independent sets and Konig--Egervary graphs
• On the Intersection of All Critical Sets of a Unicyclic Graph