On König-Egerváry collections of maximum critical independent sets

  • Vadim E. Levit Ariel University, Israel
  • Eugen Mandrescu Holon Institute of Technology, Israel
Keywords: Maximum independent set, critical set, kernel, nucleus, core, corona, diadem, König-Egerváry graph


S ⊆ V(G) is independent if no two vertices from S are adjacent. Let Ind(G) denote the family of all independent sets.

The graph G is said to be König-Egerváry if α(G) + μ(G) = |V(G)|, where α(G) denotes the size of a maximum independent set and μ(G) is the cardinality of a maximum matching. A family Γ ⊆ Ind(G) is a König-Egerváry collection if |⋃Γ| + |⋂Γ| = 2α(G).

The number d(X) = |X| − |N(X)| is the difference of X ⊆ V(G), and a set A ∈ Ind(G) is critical if d(A) = max{d(I) : I ∈ Ind(G)}.

In this paper, we show that if the family of all maximum critical independent sets of a graph G is a König-Egerváry collection, then G is a König-Egerváry graph. This result generalizes one of our conjectures verified by Short in 2016.