Download PDF - Bounds for the rainbow connection number of graphsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Bounds for the rainbow connection number of graphs

Authors 1

Affiliations

  1. Institut für Diskrete Mathematik und Algebra, Technische Universität Bergakademie Freiberg, 09596 Freiberg Germany

Abstract

An edge-coloured graph G is rainbow-connected if any two vertices are connected by a path whose edges have distinct colours. The rainbow connection number of a connected graph G, denoted rc(G), is the smallest number of colours that are needed in order to make G rainbow-connected. In this paper we show some new bounds for the rainbow connection number of graphs depending on the minimum degree and other graph parameters. Moreover, we discuss sharpness of some of these bounds.

Keywords

ENG
rainbow colouring, rainbow connectivity, extremal problem

Bibliography

  1. J.C. Bermond, On Hamiltonian Walks, Proc. of the Fifth British Combinatorial Conference, Aberdeen, 1975, Utlitas Math. XV (1976) 41-51.
  2. J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008), doi: 10.1007/978-1-84628-970-5.
  3. S. Chakraborty, E. Fischer, A. Matsliah and R. Yuster, Hardness and algorithms for rainbow connectivity, Proceedings STACS 2009, to appear in J. Combin. Optim.
  4. Y. Caro, A. Lev, Y. Roditty, Z. Tuza and R. Yuster, On rainbow connection, Electronic J. Combin. 15 (2008) #57.
  5. G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, Rainbow connection in graphs, Math. Bohemica 133 (2008) 85-98.
  6. G.A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. 2 (1952) 69-81, doi: 10.1112/plms/s3-2.1.69.
  7. A.B. Ericksen, A matter of security, Graduating Engineer & Computer Careers (2007) 24-28.
  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.
  10. V.B. Le and Z. Tuza, Finding optimal rainbow connection is hard, preprint 2009.
  11. I. Schiermeyer, Rainbow connection in graphs with minimum degree three, International Workshop on Combinatorial Algorithms, IWOCA 2009, LNCS5874 (2009) 432-437.
Discussiones Mathematicae Graph Theory
2011/31/2
Export to PBN, Opens in new tab
Pages:
387-395
Main language of publication
English
Received
2010-01-05
Accepted
2011-01-14
Published
2011

DOI: 10.7151/dmgt.1553

Exact and natural sciences