Levit and Mandrescu: Intersections and unions of critical independent sets in bipartite graphs. p. 257-260

Abstract:

Let $G$ be a simple graph with vertex set $V\left( G\right)$, and let $\mathrm{Ind}(G)$ denote the family of all independent sets of $G$. The number $d\left( X\right) =$ $\left\vert X\right\vert -\left\vert N(X)\right\vert$ is the difference of $X\subseteq V\left( G\right)$, and a set $A\in\mathrm{Ind}(G)$ is critical whenever $d(A)=\max\{d\left( I\right) :I\in\mathrm{Ind}(G)\}$ [10].

In this paper we establish various relations between intersections and unions of all critical independent sets of a bipartite graph in terms of its bipartition.

Key Words: Independent set, critical set, ker, core, diadem

2010 Mathematics Subject Classification: Primary 05C69,

Secondary 05C70