论文标题
在最小的临界独立集中，几乎是两部分非konig-egervary图
On Minimal Critical Independent Sets of Almost Bipartite non-Konig-Egervary Graphs
论文作者
论文摘要
独立数$α（g）$是最大独立集的基数，而$μ（g）$是$ g $中最大匹配的大小。如果$α（g）+μ（g）$等于$ g $的订单，则$ g $称为konig-egervary图。数字$ d \ left（g \ or右）= \ max \ {\ left \ vert a \ right \ vert \ vert - \ left \ left \ vert n \ left（a \ oright）\ right \ right \ vert：a \ subseteq v \ \ \} $称为$ g $ n \ ef n \ n \ weft（a \ weft）的关键差异（ v \ right）\ cap a \ neq \ emptyset \ right \} $）。众所周知，$α（g）-μ（g）\ leq d \ left（g \ firt）$均为每个图。图$ g $如果它具有唯一的周期，则几乎是双方的，如果它只有一个奇数循环。令$ \ mathrm {\ ker}（g）= \ bigcap \ left \ {s：s \ text {是一个关键的独立集} \ right \} $，$ \ mathrm {core} \ left（g \ weft（g \ right）$是所有最大的独立集合，以及$ \ mathrm mathrm mathrm mathrm mathrm mathrm osona corona} corona} $ g $的集合。众所周知，$ \ mathrm {\ ker}（g）\ subseteq \ mathrm {core}（g）$对于每个图是正确的，而相等性则适用于双分配图，而对于unicyclic nonicyclic nonicyclic nonicyclic nonicyclic non-konig-egervary图。在本文中，我们证明，如果$ g $是几乎是两分的非konig-egervary图，则$ \ mathrm {\ ker}（g）= $ $ \ $ \ mathrm {core}（g）$，$ \ mathrm {corona}（corona}（g）和$ \ left \ vert \ mathrm {corona}（g）\ right \ vert +\ welet \ vert \ vert \ mathrm {core}（g）（g）\ right \ vert =2α（g） +1 $。
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\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 $G$ (where $N\left( A\right) =\left\{ v:v\in V,N\left( v\right) \cap A\neq\emptyset\right\} $). It is known that $α(G)-μ(G)\leq d\left( G\right) $ 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 $\mathrm{\ker}(G)=\bigcap\left\{ S:S\text{ is a critical independent set}\right\} $, $\mathrm{core}\left( G\right) $ be the intersection of all maximum independent sets, and $\mathrm{corona}\left( G\right) $ be the union of all maximum independent sets of $G$. It is known that $\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 $G$ is an almost bipartite non-Konig-Egervary graph, then $\mathrm{\ker}(G)=$ $\mathrm{core}(G)$, $\mathrm{corona}(G)$ $\cup$ $N(\mathrm{core} \left( G\right) )=V(G)$, and $\left\vert \mathrm{corona}(G)\right\vert +\left\vert \mathrm{core}(G)\right\vert =2α(G)+1$.
