Abstract: Let G=(V,E) be a graph. A set S is independent if no two vertices from S are adjacent, alpha(G) is the size of a maximum independent set, and core(G) is the intersection of all maximum independent sets. The number d(X)=|X|-|N(X)| is the difference of the set X, and d_{c}(G)=max{d(I):I is an independent set} is called the critical difference of G. A set X is critical if d(X)=d_{c}(G). For a graph G we define ker(G) as the intersection of all critical independent sets, while diadem(G) is the union of all critical independent sets. For a bipartite graph G=(A,B,E), with bipartition {A,B}, Ore defined delta(X)=d(X) for every subset X of A, while delta_0(A)=max{delta(X):X is a subset of A}. Similarly is defined delta_0(B). In this paper we prove that for every bipartite graph G=(A,B,E) the following assertions hold: d_{c}(G)=delta_0(A)+delta_0(B); ker(G)=core(G); |ker(G)|+|diadem(G)|=2*alpha(G).
Recommendations
Cites work
- scientific article; zbMATH DE number 3172309 (Why is no real title available?)
- A characterization of the graphs in which the transversal number equals the matching number
- Combinatorial properties of the family of maximum stable sets of a graph
- Critical independent sets and König-Egerváry graphs
- Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems
- Graphs and matching theorems
- Independence numbers of graphs - an extension of the Koenig-Egervary theorem
- Vertices belonging to all critical sets of a graph
Cited in
(13)- Critical and maximum independent sets revisited
- On the structure of the minimum critical independent set of a graph
- On the critical difference of almost bipartite graphs
- Monotonic properties of collections of maximum independent sets of a graph
- scientific article; zbMATH DE number 6806045 (Why is no real title available?)
- Vertices belonging to all critical sets of a graph
- Critical hypergraphs and interesting set-pair systems
- Problems on matchings and independent sets of a graph
- Critical independent sets of König-Egerváry graphs
- On the intersection of all critical sets of a unicyclic graph
- Critical and maximum independent sets of a graph
- On critical difference, independence number and matching number of graphs
- Regular graphs with equal matching number and independence number
This page was built for publication: Critical sets in bipartite graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q368442)
