The Intersection Of Maximum Independent Set Of Several Classes Of Graphs

Suppose that G=(V(G),E(G))is a finite simple graph.An independent set in G is a set of vertices no two of which are adjacent.Denote the intersection of all the maximum independent sets of G by core(G).The number d(X)=|X|-|N(X)| is the difference of X? V(G).An independent set is critical if its difference attains maximum among all vertex subsets.Denote the intersection of all critical sets of G by ker(G).It is known that core(G)? ker(G)holds for every graph G,while core(G)=ker(G)for bipartite graphs.This paper characterizes the structure of core(G)of several classes of graphs G.In the first chapter,we introduce the research background and significance of this paper,and some basic concepts and symbolic representations.In the second chapter,we characterize the structure of a class of unicyclic graphs in which every graph G satisfies core(G)=ker(G).In the third chapter,based on the Edmonds-Gallai structure of graph,we give the structure of ker(G)and characterize the structure of almost bipartite graphs in which every graph G satisfies core(G)=ker(G).In the fourth chapter,we discuss the structure of core(G)of a class of bicyclic graphs.