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

arXiv2209.00308MaRDI QIDQ6409441FDOQ6409441

Authors: Vadim E. Levit, Eugen Mandrescu 

Publication date: 1 September 2022

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$.

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)

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)