Originators: Vadim Levit, Eugen Mandrescu (presented by Hong Liu - REGS 2009)
Definitions: A graph G is a König-Egerváry graph if has exactly α(G)+α'(G) vertices, where α(G) is the maximum size of an independent set of vertices in G and α'(G) is the maximum size of a matching. Every matching leaves at least |V(G)|-2α'(G) vertices uncovered, and this value is the deficiency of G, written def(G). The critical difference of G, written d(G), is the maximum of |S|-|N(S)| over all independent sets S, where N(S) denotes the set of vertices having at least one neighbor in S. An independent set is critical if it achieves this maximum. Let αc(G) be the maximum size of a critical independent set.
Background: The well-known König-Egerváry Theorem [K,E] implies that every bipartite graph is a König-Egerváry graph, but there are also non-bipartite graphs in this class. For example, the graph obtained from a 5-cycle by adding two pendant edges at one vertex and one pendant edge at a vertex not adjacent to it is also a König-Egerváry graph. Trivially, αc(G)≤α(G) for every graph G; Larson [L] proved that G is a König-Egerváry graph if and only if αc(G)=α(G). Levit and Mandrescu [LM2] proved that
d(G) = |C(G)|-|N(C(G))| = α(G)-α'(G) = def(G) (*)
for every König-Egerváry graph G, where C(G) is the set of vertices belonging to all maximum-sized independent sets. They also proved that for every König-Egerváry graph, not only is some maximum independent set critical, but in fact every maximum independent set is critical.
Question: Does there exist a graph satisfying (*) that is not a König-Egerváry graph? If not, then (*) characterizes König-Egerváry graphs.
Comments: The set C(G), called the core of G, is studied also in [LM1]. Critical independent sets are studied in [Z].
References:
[K] D. König, Graphen und Matrizen,
Matematikai Lapok 38(1931) 116-119.
[E] E. Egerváry,
On combinatorial properties of matrices,
Matematikai Lapok 38(1931) 16-28.
[L] C. E. Larson, A new characterization of König-Egerváry
graphs, The 2nd Canadian Discrete and Algorithmic Mathematics Conference,
May 25-28, 2009, CRM Montreal (Canada).
[LM1] V.E. Levit, E. Mandrescu, Combinatorial properties of the family of
maximum stable sets of a graph, Discrete Appl. Math. 117(2002) 149-161.
[LM2] V.E.Levit, E.Mandrescu, Critical independent sets and
König-Egerváry graphs, arXiv:0906.4609v2 [math.CO] 30 June 2009.
[Z] C.Q.Zhang, Finding critical independent sets and critical vertex
subsets are polynomial problems, SIAM J.Discrete Mathematics 3(1990)
431-438.