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 .