On the intersection of all critical sets of a unicyclic graph

DOI10.1016/J.DAM.2013.09.006zbMATH Open1300.05231arXiv1108.3756OpenAlexW2093275204MaRDI QIDQ741775FDOQ741775

Authors: Vadim E. Levit, Eugen Mandrescu 

Publication date: 12 September 2014

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

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.

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

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

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)

Cites Work

• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems
• Combinatorial properties of the family of maximum stable sets of a graph
• On \(\alpha^{+}\)-stable König-Egerváry graphs
• Critical independent sets and König-Egerváry graphs
• On maximum matchings in König-Egerváry graphs
• On the core of a unicyclic graph
• 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
• Vertices belonging to all critical sets of a graph
• Critical sets in bipartite graphs
• On the number of vertices belonging to all maximum stable sets of a graph
• On \(\alpha\)-critical edges in König--Egerváry graphs
• A set and collection lemma
• Greedoids on Vertex Sets of Unicycle Graphs
• Revolutionaries and spies on trees and unicyclic graphs
• On the structure of the minimum critical independent set of a graph

Cited In (8)

• On König-Egerváry collections of maximum critical independent sets
• Problems on matchings and independent sets of a graph
• Title not available (Why is that?)
• On the core of a unicyclic graph
• Critical independent sets of König-Egerváry graphs
• 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)