The direct product of graphs G = (V (G),E(G)) and H = (V (H),E(H)) is the graph, denoted as G×H, with vertex set V (G×H) = V (G)×V (H), where vertices (x_(1), y_(1)) and (x_(2), y_(2)) are adjacent in G × H if x_(1)x_(2) ∈ E(G) and y_(1)y_(2) ∈ E(H). Let n be odd and m even. We prove that every maximum independent set in P_(n)×G, respectively C_(m)×G, is of the form (A×C)∪(B× D), where C and D are nonadjacent in G, and A∪B is the bipartition of P_(n) respectively C_(m). We also give a characterization of maximum independent subsets of P_(n) × G for every even n and discuss the structure of maximum independent sets in T × G where T is a tree.
展开▼
