On the core of a unicyclic graph

DOI10.26493/1855-3974.201.6E1zbMATH Open1258.05096arXiv1102.4727OpenAlexW2106533361WikidataQ129360821 ScholiaQ129360821MaRDI QIDQ4906181FDOQ4906181

Authors: Vadim E. Levit, Eugen Mandrescu 

Publication date: 7 February 2013

Published in: Ars Mathematica Contemporanea (Search for Journal in Brave)

Abstract: A set S is independent in a graph G if no two vertices from S are adjacent. By core(G) we mean the intersection of all maximum independent sets. 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. A connected graph having only one cycle, say C, is a unicyclic graph. In this paper we prove that if G is a unicyclic graph of order n and n-1 = alpha(G) + mu(G), then core(G) coincides with the union of cores of all trees in G-C.

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

Recommendations

• On the intersection of all critical sets of a unicyclic graph
• Some results on the independence polynomial of unicyclic graphs
• The numbers of maximal independent sets in connected unicyclic graphs
• The number of independent sets in unicyclic graphs
• Vertices belonging to all critical sets of a graph

zbMATH Keywords

matchingcoreunicyclic graphmaximum independent setKönig-Egerváry graph.

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)

Cited In (8)

• The core of a graph
• On local maximum stable set greedoids
• 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
• Title not available (Why is that?)
• 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 core of a unicyclic graph

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