一类单圈图的最大独立集的交  

The intersection of maximum independent set of a class of unicyclic graphs

作　　者：谢佳漫 王艳 XIE Jia-man;WANG Yan(School of Mathematics and Statistics,Minnan Normal University,Zhangzhou 363000,China)

机构地区：[1]闽南师范大学数学与统计学院,福建漳州363000

出　　处：《青海师范大学学报（自然科学版）》2021年第2期19-23,共5页Journal of Qinghai Normal University(Natural Science Edition)

基　　金：福建省自然科学基金(2020J01795)。

摘　　要：设G=(V(G),E(G))为有限简单图,X是V(G)的子集.若X中任意两个点不相邻则称X是独立集.用core(G)表示G的所有最大独立集的交.X的差是指X的顶点数与其邻集的顶点数之差.在G的所有顶点子集中,差最大的子集即为G的临界集.用ker(G)表示G的所有临界集的交.在图G中,core(G)ker(G);当图G为二部图时,则core(G)=ker(G).本文刻画了一类单圈图G的core(G)=ker(G)的结构.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 a class of unicyclic graphs in which every graph G satisfies core(G)=ker(G).

关 键 词：临界集 最大独立集 单圈图 完美匹配 

分 类 号：O157.5[理学—数学]