On the intersection of all critical sets of a unicyclic graph

DOI10.1016/J.DAM.2013.09.006MaRDI QIDQ741775zbMATH OpenOpenAlexFDO

Authors 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

coronacoreunicyclic graphcritical setmaximum independent setKönig-Egerváry graph

Mathematics Subject Classification ID

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

Abstract: A set S is independent in a graph G if no two vertices from S are adjacent. The independence number alpha(G) is the cardinality of a maximum independent set, while mu(G) is the size of a maximum matching in G. If alpha(G)+mu(G)=|V|, then G=(V,E) is called a Konig-Egervary graph. The number d_{c}(G)=max{|A|-|N(A)|} is called the critical difference of G (Zhang, 1990). By core(G) (corona(G)) we denote the intersection (union, respectively) of all maximum independent sets, while by ker(G) we mean the intersection of all critical independent sets. A connected graph having only one cycle is called unicyclic. It is known that ker(G) is a subset of core(G) for every graph G, while the equality is true for bipartite graphs (Levit and Mandrescu, 2011). For Konig-Egervary unicyclic graphs, the difference |core(G)|-|ker(G)| may equal any non-negative integer. In this paper we prove that if G is a non-Konig-Egervary unicyclic graph, then: (i) ker(G)= core(G) and (ii) |corona(G)|+|core(G)|=2*alpha(G)+1. Pay attention that |corona(G)|+|core(G)|=2*alpha(G) holds for every Konig-Egervary graph.

Recommendations

• On the core of a unicyclic graph
• Problems on matchings and independent sets of a graph
• Critical independent sets of König-Egerváry graphs
• On the critical difference of almost bipartite graphs
• Vertices belonging to all critical sets of a graph

Cites work

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

Cited in

(8)

• Problems on matchings and independent sets of a graph
• On König-Egerváry collections of maximum critical independent sets
• scientific article; zbMATH DE number 6806045 (Why is no real title available?)
• Critical independent sets of König-Egerváry graphs
• On the core of a unicyclic graph
• Critical and maximum independent sets of a graph
• Computing unique maximum matchings in O(m) time for König-Egerváry graphs and unicyclic graphs
• Monotonic properties of collections of maximum independent sets of a graph

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

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