VERTICES BELONGING TO ALL CRITICAL SETS OF A GRAPH.

Let G = (V, E) be a graph. A set S⊆V is independent if no two vertices from are adjacent, while core(G) is the intersection of all maximum independent sets [V. E. Levit and E. Mandrescu, Discrete Appl. Math., 117 (2002), pp. 149-161]. The independence number α(G)is the cardinality of a largest independent set, and µ(G) is the size of a maximum matching of G. The neighborhood of A⊆V is N(A)= {v ∈ V : N(v)∩=0. The number dc(G)=max{|X|-|N(X)| : X ⊆ V} is called the critical di?erence of G, and is critical if |A|-|N(A)| = dc(G) [C. Q. Zhang, SIAM J. Discrete Math., 3 (1990), pp. 431-438]. We define ker(G) as the intersection of all critical sets. In this paper we prove that if dc(G) ≥ 1, then ker(G) ⊆ core(G) and |ker(G)| >dc(G) ≥ α(G)-µ(G). [ABSTRACT FROM AUTHOR]