Vertices belonging to all critical sets of a graph

DOI10.1137/110823560MaRDI QIDQ2902909zbMATH OpenOpenAlexFDO

Authors Vadim E. Levit, Eugen Mandrescu

Publication date 22 August 2012

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

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)

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.

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

Cited in

(16)

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