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

MaRDI QIDQ6409441zbMATH OpenFDO

Authors Vadim E. Levit, Eugen Mandrescu

Publication date 1 September 2022

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: The independence number $alpha(G)$ is the cardinality of a maximum independent set, while $mu(G)$ is the size of a maximum matching in $G$. If $alpha(G)+mu(G)$ equals the order of $G$, then $G$ is called a Konig-Egervary graph. The number $dleft(Gight)=maxleftvertAightvert-leftvertNleft(Aight)ightvert:AsubseteqV$ is called the critical difference of $G$ (where $Nleft(Aight)=leftv:vinV,Nleft(vight)capAeqemptysetight$). It is known that $alpha(G)-mu(G)leqdleft(Gight)$ 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 $$, $mathrmcoreleft(Gight)$ be the intersection of all maximum independent sets, and $mathrmcoronaleft(Gight)$ be the union of all maximum independent sets of $G$. It is known that $mathrmker(G)subseteqmathrmcore(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 $mathrmker(G)=$ $mathrmcore(G)$, $mathrmcorona(G)$ $cup$ $N(mathrmcoreleft(Gight))=V(G)$, and $leftvertmathrmcorona(G)ightvert+leftvertmathrmcore(G)ightvert=2alpha(G)+1$.

This page was built for publication: On Minimal Critical Independent Sets of Almost Bipartite non-Konig-Egervary Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6409441)