On Minimal Critical Independent Sets of Almost Bipartite non-Konig-Egervary Graphs

preprint2022arXivOpen access

Abstract

The independence number α(G)α(G) is the cardinality of a maximum independent set, while μ(G)μ(G) is the size of a maximum matching in GG. If α(G)+μ(G)α(G)+μ(G) equals the order of GG, then GG is called a Konig-Egervary graph. The number d(G)=max⁡{∣A∣−∣N(A)∣:A⊆V}d\left( G\right) =\max\{\left\vert A\right\vert -\left\vert N\left( A\right) \right\vert :A\subseteq V\} is called the critical difference of GG (where N(A)={v:v∈V,N(v)∩A≠∅}N\left( A\right) =\left\{ v:v\in V,N\left( v\right) \cap A\neq\emptyset\right\} ). It is known that α(G)−μ(G)≤d(G)α(G)-μ(G)\leq d\left( G\right) holds for every graph. A graph GG is unicyclic if it has a unique cycle and almost bipartite if it has only one odd cycle. Let ker⁡(G)=⋂{S:S is a critical independent set}\mathrm{\ker}(G)=\bigcap\left\{ S:S\text{ is a critical independent set}\right\} , core(G)\mathrm{core}\left( G\right) be the intersection of all maximum independent sets, and corona(G)\mathrm{corona}\left( G\right) be the union of all maximum independent sets of GG. It is known that ker⁡(G)⊆core(G)\mathrm{\ker}(G)\subseteq\mathrm{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 GG is an almost bipartite non-Konig-Egervary graph, then ker⁡(G)=\mathrm{\ker}(G)= core(G)\mathrm{core}(G), corona(G)\mathrm{corona}(G) ∪\cup N(core(G))=V(G)N(\mathrm{core} \left( G\right) )=V(G), and ∣corona(G)∣+∣core(G)∣=2α(G)+1\left\vert \mathrm{corona}(G)\right\vert +\left\vert \mathrm{core}(G)\right\vert =2α(G)+1.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.