On the rainbow connection of Cartesian products and their subgraphs

Sandi Klavžar; Gašper Mekiš

Discussiones Mathematicae Graph Theory (2012)

  • Volume: 32, Issue: 4, page 783-793
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Sandi Klavžar, and Gašper Mekiš. "On the rainbow connection of Cartesian products and their subgraphs." Discussiones Mathematicae Graph Theory 32.4 (2012): 783-793. <http://eudml.org/doc/270945>.

@article{SandiKlavžar2012,
abstract = {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.},
author = {Sandi Klavžar, Gašper Mekiš},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {rainbow connection; strong rainbow connection; Cartesian product of graphs; isometric subgraph; hypercube},
language = {eng},
number = {4},
pages = {783-793},
title = {On the rainbow connection of Cartesian products and their subgraphs},
url = {http://eudml.org/doc/270945},
volume = {32},
year = {2012},
}

TY - JOUR
AU - Sandi Klavžar
AU - Gašper Mekiš
TI - On the rainbow connection of Cartesian products and their subgraphs
JO - Discussiones Mathematicae Graph Theory
PY - 2012
VL - 32
IS - 4
SP - 783
EP - 793
AB - 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.
LA - eng
KW - rainbow connection; strong rainbow connection; Cartesian product of graphs; isometric subgraph; hypercube
UR - http://eudml.org/doc/270945
ER -

References

top
  1. [1] M. Basavaraju, L.S. Chandran, D. Rajendraprasad and A. Ramaswamy, Rainbow connection number of graph power and graph products, manuscript (2011) arXiv:1104.4190 [math.CO]. Zbl1306.05203
  2. [2] Y. Caro, A. Lev, Y. Roditty, Z. Tuza and R. Yuster, On rainbow connection, Electron. J. Combin. 15 (2008) #R57. Zbl1181.05037
  3. [3] S. Chakraborty, E. Fischer, A. Matsliah and R. Yuster, Hardness and algorithms for rainbow connection, J. Comb. Optim. 21 (2011) 330-347, doi: 10.1007/s10878-009-9250-9. Zbl1319.05049
  4. [4] G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, Rainbow connection in graphs, Math. Bohem. 133 (2008) 85-98. Zbl1199.05106
  5. [5] T. Gologranc, G. Mekiš and I. Peterin, Rainbow connection and graph products, IMFM Preprint Series 49 (2011) #1149. 
  6. [6] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs: Second Edition (CRC Press, Boca Raton, 2011). Zbl1283.05001
  7. [7] W. Imrich, S. Klavžar and D.F. Rall, Topics in Graph Theory: Graphs and Their Cartesian Products (A K Peters, Wellesley, 2008). Zbl1156.05001
  8. [8] A. Kemnitz and I. Schiermeyer, Graphs with rainbow connection number two, Discuss. Math. Graph Theory 31 (2011) 313-320, doi: 10.7151/dmgt.1547. 
  9. [9] M. Krivelevich and R. Yuster, The rainbow connection of a graph is (at most) reciprocal to its minimum degree, J. Graph Theory 63 (2010) 185-191, doi: 10.1002/jgt.20418. Zbl1193.05079
  10. [10] X. Li and Y. Sun, Characterize graphs with rainbow connection number m-2 and rainbow connection numbers of some graph operations, manuscript (2010). 
  11. [11] X. Li and Y. Sun, Rainbow connection of graphs - A survey, manuscript (2011) arXiv:1101.5747v1 [math.CO]. 
  12. [12] I. Schiermeyer, Bounds for the rainbow connection number of graphs, Discuss. Math. Graph Theory 31 (2011) 387-395, doi: 10.7151/dmgt.1553. Zbl1234.05132
  13. [13] P. Winkler, Isometric embedding in products of complete graphs, Discrete Appl. Math. 7 (1984) 221-225. Zbl0529.05055

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.