Geodesic
On the rainbow connection of Cartesian products and their subgraphs
Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 4, pp. 783-793

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: rainbow connection, strong rainbow connection, Cartesian product of graphs, isometric subgraph, hypercube 
@article{DMGT_2012_32_4_a12,
     author = {Klav\v{z}ar, Sandi and Meki\v{s}, Ga\v{s}per},
     title = {On the rainbow connection of {Cartesian} products and their subgraphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {783--793},
     publisher = {mathdoc},
     volume = {32},
     number = {4},
     year = {2012},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a12/}
}
TY  - JOUR
AU  - Klavžar, Sandi
AU  - Mekiš, Gašper
TI  - On the rainbow connection of Cartesian products and their subgraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2012
SP  - 783
EP  - 793
VL  - 32
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a12/
LA  - en
ID  - DMGT_2012_32_4_a12
ER  - 
%0 Journal Article
%A Klavžar, Sandi
%A Mekiš, Gašper
%T On the rainbow connection of Cartesian products and their subgraphs
%J Discussiones Mathematicae. Graph Theory
%D 2012
%P 783-793
%V 32
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a12/
%G en
%F DMGT_2012_32_4_a12
Klavžar, Sandi; Mekiš, Gašper. On the rainbow connection of Cartesian products and their subgraphs. Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 4, pp. 783-793. http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a12/