On the Core of a Unicyclic Graph

2011/02/23 by Levit, Vadim E., Mandrescu, Eugen
#05C69 (Primary) 05C70(Secondary) #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2

paper · doi:10.48550/arxiv.1102.4727

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.

Related

• On the Intersection of All Critical Sets of a Unicyclic Graph
• Vertices Belonging to All Critical Independent Sets of a Graph
• An Algorithm Computing the Core of a Konig-Egervary Graph
• On the Structure of the Minimum Critical Independent Set of a Graph
• Critical and Maximum Independent Sets of a Graph