On the intersection of all critical sets of a unicyclic graph

DOI10.1016/j.dam.2013.09.006zbMath1300.05231arXiv1108.3756OpenAlexW2093275204MaRDI QIDQ741775

Vadim E. Levit, Eugen Mandrescu

Publication date: 12 September 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

coronacorecritical setmaximum independent setunicyclic graphKönig-Egerváry graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (6)

Critical independent sets of König-Egerváry graphs ⋮ Computing unique maximum matchings in \(O(m)\) time for König-Egerváry graphs and unicyclic graphs ⋮ Critical and maximum independent sets of a graph ⋮ Problems on matchings and independent sets of a graph ⋮ On König-Egerváry collections of maximum critical independent sets ⋮ Monotonic properties of collections of maximum independent sets of a graph

Cites Work

• Critical sets in bipartite graphs
• A set and collection lemma
• A characterization of the graphs in which the transversal number equals the matching number
• The smallest values of algebraic connectivity for unicyclic graphs
• The number of independent sets of unicyclic graphs with given matching number
• Minimizing the least eigenvalue of unicyclic graphs with fixed diameter
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• Combinatorial properties of the family of maximum stable sets of a graph
• On the number of vertices belonging to all maximum stable sets of a graph
• On \(\alpha^{+}\)-stable König-Egerváry graphs
• Critical independent sets and König-Egerváry graphs
• Revolutionaries and spies on trees and unicyclic graphs
• On the structure of the minimum critical independent set of a graph
• On maximum matchings in König-Egerváry graphs
• On \(\alpha\)-critical edges in König--Egerváry graphs
• Vertices Belonging to All Critical Sets of a Graph
• Greedoids on Vertex Sets of Unicycle Graphs
• Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems
• On the core of a unicyclic graph

This page was built for publication: On the intersection of all critical sets of a unicyclic graph