On the Intersection of All Critical Sets of a Unicyclic Graph

Details On the Intersection of All Critical Sets of a Unicyclic Graph On the Intersection of All Critical Sets of a Unicyclic Graph

2011-08-18

arxiv.org/abs/1108.3756v1

Computer Science

Discrete Mathematics

8 pages, 5 figures

Scientific paper

A set S is independent in a graph G if no two vertices from S are adjacent. 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. If alpha(G)+mu(G)=|V|, then G=(V,E) is called a Konig-Egervary graph. The number d_{c}(G)=max{|A|-|N(A)|} is called the critical difference of G (Zhang, 1990). By core(G) (corona(G)) we denote the intersection (union, respectively) of all maximum independent sets, while by ker(G) we mean the intersection of all critical independent sets. A connected graph having only one cycle is called unicyclic. It is known that ker(G) is a subset of core(G) for every graph G, while the equality is true for bipartite graphs (Levit and Mandrescu, 2011). For Konig-Egervary unicyclic graphs, the difference |core(G)|-|ker(G)| may equal any non-negative integer. In this paper we prove that if G is a non-Konig-Egervary unicyclic graph, then: (i) ker(G)= core(G) and (ii) |corona(G)|+|core(G)|=2*alpha(G)+1. Pay attention that |corona(G)|+|core(G)|=2*alpha(G) holds for every Konig-Egervary graph.

Affiliated with

Also associated with

No associations

Rating

On the Intersection of All Critical Sets of a Unicyclic Graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Intersection of All Critical Sets of a Unicyclic Graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Intersection of All Critical Sets of a Unicyclic Graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-181404