Critical sets in bipartite graphs

DOI10.1007/S00026-013-0195-4zbMATH Open1272.05151arXiv1102.1138OpenAlexW1670478499MaRDI QIDQ368442FDOQ368442

Authors: Vadim E. Levit, Eugen Mandrescu 

Publication date: 23 September 2013

Published in: Annals of Combinatorics (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/1102.1138

Recommendations

• scientific article; zbMATH DE number 6806045
• Vertices belonging to all critical sets of a graph
• Critical and maximum independent sets revisited
• Critical independent sets of König-Egerváry graphs
• On the structure of the minimum critical independent set of a graph

zbMATH Keywords

matchingindependent setcritical set

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)

Cites Work

• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• Title not available (Why is that?)
• Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems
• Combinatorial properties of the family of maximum stable sets of a graph
• Critical independent sets and König-Egerváry graphs
• A characterization of the graphs in which the transversal number equals the matching number
• Vertices belonging to all critical sets of a graph
• Graphs and matching theorems

Cited In (13)

• Critical hypergraphs and interesting set-pair systems
• Problems on matchings and independent sets of a graph
• Title not available (Why is that?)
• On critical difference, independence number and matching number of graphs
• Critical and maximum independent sets revisited
• Vertices belonging to all critical sets of a graph
• Critical independent sets of König-Egerváry graphs
• On the critical difference of almost bipartite graphs
• Critical and maximum independent sets of a graph
• On the intersection of all critical sets of a unicyclic graph
• On the structure of the minimum critical independent set of a graph
• Monotonic properties of collections of maximum independent sets of a graph
• 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)