2014/07/28 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.1407.7368
Let G be a simple graph with vertex set V( G) . A set S⊆ V( G) is independent if no two vertices from S are adjacent, and by Ind(G) we mean the family of all independent sets of G. The number d( X) = \vert X\vert -\vert N(X)\vert is the difference of X⊆ V( G) , and a set A\inInd(G) is critical if d(A)=max \d( I) :I\inInd(G)\ (Zhang, 1990). Let us recall the following definitions: core( G) = \bigcap S : S is a maximum independent set. corona( G) = \bigcup S :S is a maximum independent set. ker(G) = \bigcap S : S is a critical independent set. diadem(G) = \bigcup S : S is a critical independent set. In this paper we present various structural properties of ker(G), in relation with core( G) , corona( G) , and diadem(G).