PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2012 | 32 | 4 | 783-793
Tytuł artykułu

On the rainbow connection of Cartesian products and their subgraphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Wydawca
Rocznik
Tom
32
Numer
4
Strony
783-793
Opis fizyczny
Daty
wydano
2012
otrzymano
2011-06-08
poprawiono
2012-02-06
zaakceptowano
2012-02-06
Twórcy
  • Faculty of Mathematics and Physics, University of Ljubljana, Jadranska 19, 1000 Ljubljana, Slovenia
  • Faculty of Natural Sciences and Mathematics, University of Maribor, Koroška 160, 2000 Maribor, Slovenia
  • Institute of Mathematics, Physics and Mechanics, Jadranska 19, 1000 Ljubljana
Bibliografia
  • [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].
  • [2] Y. Caro, A. Lev, Y. Roditty, Z. Tuza and R. Yuster, On rainbow connection, Electron. J. Combin. 15 (2008) #R57.
  • [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.
  • [4] G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, Rainbow connection in graphs, Math. Bohem. 133 (2008) 85-98.
  • [5] T. Gologranc, G. Mekiš and I. Peterin, Rainbow connection and graph products, IMFM Preprint Series 49 (2011) #1149.
  • [6] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs: Second Edition (CRC Press, Boca Raton, 2011).
  • [7] W. Imrich, S. Klavžar and D.F. Rall, Topics in Graph Theory: Graphs and Their Cartesian Products (A K Peters, Wellesley, 2008).
  • [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] 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.
  • [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] X. Li and Y. Sun, Rainbow connection of graphs - A survey, manuscript (2011) arXiv:1101.5747v1 [math.CO].
  • [12] I. Schiermeyer, Bounds for the rainbow connection number of graphs, Discuss. Math. Graph Theory 31 (2011) 387-395, doi: 10.7151/dmgt.1553.
  • [13] P. Winkler, Isometric embedding in products of complete graphs, Discrete Appl. Math. 7 (1984) 221-225.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1644
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.