Vertices belonging to all critical sets of a graph

DOI10.1137/110823560zbMATH Open1246.05122arXiv1102.0401OpenAlexW2031361115MaRDI QIDQ2902909FDOQ2902909

Authors: Vadim E. Levit, Eugen Mandrescu 

Publication date: 22 August 2012

Published in: SIAM Journal on Discrete Mathematics (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. The independence number alpha(G) is the cardinality of a maximum independent set, and mu(G) is the size of a maximum matching. The number id_{c}(G)=max{|I|-|N(I)|:I is an independent set} is called the critical independence difference of G, and A is critical if |A|-|N(A)|=id_{c}(G). We define core(G) as the intersection of all maximum independent sets, and ker(G)as the intersection of all critical independent sets. In this paper we prove that if a graph G is non-quasi-regularizable (i.e., there exists some independent set A, such that |A|>|N(A)|), then: ker(G) is a subset of core(G), and |ker(G)|> id_{c}(G) >= alpha(G)-mu(G) > 0.

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

Recommendations

• Critical and maximum independent sets revisited
• On the structure of the minimum critical independent set of a graph
• Critical sets in bipartite graphs
• Critical and maximum independent sets of a graph
• Critical independent sets of König-Egerváry graphs

zbMATH Keywords

independent setcritical setmaximum matchingcritical difference

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) Combinatorial inequalities (05A20)

Cited In (16)

• Blocking independent sets for \(H\)-free graphs via edge contractions and vertex deletions
• On an annihilation number conjecture
• On König-Egerváry collections of maximum critical independent sets
• Problems on matchings and independent sets of a graph
• On some conjectures concerning critical independent sets of a graph
• On critical difference, independence number and matching number of graphs
• Critical and maximum independent sets revisited
• On the core of a unicyclic graph
• Critical independent sets of König-Egerváry graphs
• Contraction and deletion blockers for perfect graphs and \(H\)-free 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
• Critical sets in bipartite graphs

This page was built for publication: Vertices belonging to all critical sets of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2902909)