- Tytuł:
- Maximum Independent Sets in Direct Products of Cycles or Trees with Arbitrary Graphs
- Autorzy:
-
Paj, Tjaša
Špacapan, Simon - Powiązania:
- https://bibliotekanauki.pl/articles/31339257.pdf
- Data publikacji:
- 2015-11-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
direct product
independent set - Opis:
- 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 (x1, y1) and (x2, y2) are adjacent in G × H if x1x2 ∈ E(G) and y1y2 ∈ E(H). Let n be odd and m even. We prove that every maximum independent set in Pn×G, respectively Cm×G, is of the form (A×C)∪(B×D), where C and D are nonadjacent in G, and A∪B is the bipartition of Pn respectively Cm. We also give a characterization of maximum independent subsets of Pn × G for every even n and discuss the structure of maximum independent sets in T × G where T is a tree.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2015, 35, 4; 675-688
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki