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

Two Disjoint Maximal Independent Sets in Vertex -Transitive Graphs

  • 摘要: C.Berp,E.J.Ockayne和S.T.Hedetniemi猜想每个非空点可迁图包含两个不相交的极大独立点集.本文证明了下面的结果: 1.设L在V(G)上可迁且为交换群,则G有两个不相交的极大独立点集。 2.设L在V(G)上可迁且为幂零群,则G有两个不相交的极大独立点集。 3.p~k阶(p为素数)非空点可迁图包含两个不相交的极大独立点集。

     

    Abstract: 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 .

     

/

返回文章
返回
Baidu
map