tailieunhanh - Báo cáo toán học: " On rainbow connection"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: On rainbow connection. | On rainbow connection Yair Caro Department of Mathematics University of Haifa-Oranim Tivon 36006 Israel yacaro@ Arie Lev Department of Computer Sciences Tel Aviv University and The Academic College of Tel-Aviv-Yaffo Tel-Aviv 61161 Israel Yehuda Roditty Department of Computer Sciences Tel Aviv University and The Academic College of Tel-Aviv-Yaffo Tel-Aviv 61161 Israel jr@ Zsolt Tuza Hungarian Academy of Sciences and University of Pannonia Budapest Hungary jr@ Raphael Yuster Department of Mathematics University Haifa Haifa 31905 Israel raphy@ Submitted Nov 14 2007 Accepted Apr 6 2008 Published Apr 18 2008 Mathematics Subject Classification 05C15 05C40 Abstract An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph G denoted rc G is the smallest number of colors that are needed in order to make G rainbow connected. In this paper we prove several non-trivial upper bounds for rc G as well as determine sufficient conditions that guarantee rc G 2. Among our results we prove that if G is a connected graph with n vertices and with minimum degree 3 then rc G 5n 6 and if the minimum degree is Ỗ then rc G nrn 1 os 1 . We also determine the threshold function for a random graph to have rc G 2 and make several conjectures concerning the computational complexity of rainbow connection. Research supported in part by the Hungarian Scientific Research Fund OTKA grant T-049613 THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 R57 1 1 Introduction All graphs in this paper are finite undirected and simple. We follow the notation and terminology of 2 . Connectivity is perhaps the most fundamental graph-theoretic property. There are many ways to strengthen the connectivity property such as requiring hamiltonicity k-connectivity imposing bounds on the diameter requiring the existence of edge-disjoint spanning trees and so .