- Tytuł:
- On the rainbow connection of Cartesian products and their subgraphs
- Autorzy:
-
Klavžar, Sandi
Mekiš, Gašper - Powiązania:
- https://bibliotekanauki.pl/articles/743307.pdf
- Data publikacji:
- 2012
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
rainbow connection
strong rainbow connection
Cartesian product of graphs
isometric subgraph
hypercube - Opis:
- Rainbow connection number of Cartesian products and their subgraphs are considered. Previously known bounds are compared and non-existence of such bounds for subgraphs of products are discussed. It is shown that the rainbow connection number of an isometric subgraph of a hypercube is bounded above by the rainbow connection number of the hypercube. Isometric subgraphs of hypercubes with the rainbow connection number as small as possible compared to the rainbow connection of the hypercube are constructed. The concept of c-strong rainbow connected coloring is introduced. In particular, it is proved that the so-called Θ-coloring of an isometric subgraph of a hypercube is its unique optimal c-strong rainbow connected coloring.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2012, 32, 4; 783-793
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł