On the core of a unicyclic graph

Vadim E. Levit, Eugen Mandrescu


A set SV is independent in a graph G = (V, E) if no two vertices from S are adjacent. By core(G) we mean the intersection of all maximum independent sets. The independence number α(G) is the cardinality of a maximum independent set, while μ(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 = α(G) + μ(G), then core(G) coincides with the union of cores of all trees in GC.


maximum independent set, core, matching, unicyclic graph, Konig-Egervary graph

Full Text:


DOI: https://doi.org/10.26493/1855-3974.201.6e1

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications