On the core of a unicyclic graph

DOI10.26493/1855-3974.201.6E1MaRDI QIDQ4906181zbMATH OpenOpenAlexWikidataFDO

Authors Vadim E. Levit, Eugen Mandrescu

Publication date 7 February 2013

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

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

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)

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.

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

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
• Computing unique maximum matchings in O(m) time for König-Egerváry graphs and unicyclic graphs
• scientific article; zbMATH DE number 7708854 (Why is no real title available?)
• 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)