On Minimal Critical Independent Sets of Almost Bipartite non-Konig-Egervary Graphs
share
The independence number α(G) is the cardinality of a maximum independent set, while μ(G) is the size of a maximum matching in G. If α(G)+μ(G) equals the order of G, then G is called a Konig-Egervary graph. The number d( G) =max{| A| -| N( A) | :A⊆ V} is called the critical difference of G (where N( A) ={ v:v∈ V,N( v) ∩ A≠∅}). It is known that α(G)-μ(G)≤ d( G) holds for every graph. A graph G is unicyclic if it has a unique cycle and almost bipartite if it has only one odd cycle. Let (G)=⋂{ S:S is a critical independent set}, core( G) be the intersection of all maximum independent sets, and corona( G) be the union of all maximum independent sets of G. It is known that (G)⊆core(G) is true for every graph, while the equality holds for bipartite graphs, and for unicyclic non-Konig-Egervary graphs. In this paper, we prove that if G is an almost bipartite non-Konig-Egervary graph, then (G)= core(G), corona(G) ∪ N(core( G) )=V(G), and |corona(G)| +|core(G)| =2α(G)+1.
READ FULL TEXT