点可迁图中的两个不相交的极大独立点集(英文)  

Two Disjoint Maximal Independent Sets in Vertex -Transitive Graphs

作　　者：王朝瑞[1] 石民勇[1] 

机构地区：[1]北京理工大学应用数学系

出　　处：《北京理工大学学报》1991年第3期65-69,共5页Transactions of Beijing Institute of Technology

摘　　要：C.Berp,E.J.Ockayne和S.T.Hedetniemi猜想每个非空点可迁图包含两个不相交的极大独立点集.本文证明了下面的结果: 1.设L在V(G)上可迁且为交换群,则G有两个不相交的极大独立点集。 2.设L在V(G)上可迁且为幂零群,则G有两个不相交的极大独立点集。 3.p^k阶(p为素数)非空点可迁图包含两个不相交的极大独立点集。C . Berge , E. J . Cockayne and S . T . Hedetniemi conjectured that every nonempty vertex-transitive graph contains two maximal independent vertex sets .The following results are proved : (1) Let L be transitive on V(G) and Abelian , then G has two disjoint maximal independent sets , and each contains a. vertices , (where a is the independence number of G) . (2) Let L be transitive on V (G) and nilpotent , then G has two disjoint maximal independent sets . (3) A nonempty vertex-transitive graph of order pk ,p a prime , contains two disjoint maximal independent sets .

关 键 词：点可迁图 独立点集 交换群 幂零群 

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