Premium
Primitivity and independent sets in direct products of vertex‐transitive graphs
Author(s) -
Zhang Huajun
Publication year - 2011
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20526
Subject(s) - combinatorics , mathematics , transitive relation , vertex (graph theory) , maximal independent set , discrete mathematics , independent set , graph , chordal graph , 1 planar graph
We introduce the concept of the primitivity of independent set in vertex‐transitive graphs, and investigate the relationship between the primitivity and the structure of maximum independent sets in direct products of vertex‐transitive graphs. As a consequence of our main results, we positively solve an open problem related to the structure of independent sets in powers of vertex‐transitive graphs. © 2010 Wiley Periodicals, Inc. J Graph Theory 67: 218‐225, 2011