Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Maximum Independent Sets in Direct Products of Cycles or Trees with Arbitrary Graphs

100%

Paj T., Špacapan S.

Discussiones Mathematicae Graph Theory

2015

tom 35

nr 4

675-688

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.

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

On acyclic colorings of direct products

100%

Špacapan S., Horvat A.

Discussiones Mathematicae Graph Theory

2008

tom 28

nr 2

323-333

A coloring of a graph G is an acyclic coloring if the union of any two color classes induces a forest. It is proved that the acyclic chromatic number of direct product of two trees T₁ and T₂ equals min{Δ(T₁) + 1, Δ(T₂) + 1}. We also prove that the acyclic chromatic number of direct product of two complete graphs Kₘ and Kₙ is mn-m-2, where m ≥ n ≥ 4. Several bounds for the acyclic chromatic number of direct products are given and in connection to this some questions are raised.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

2 Špacapan S.

1 Horvat A.

1 Paj T.

1 2015

1 2008

Wyniki wyszukiwania

Maximum Independent Sets in Direct Products of Cycles or Trees with Arbitrary Graphs

On acyclic colorings of direct products