Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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@kvgeva.org.il 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@post.tau.il Zsolt Tuza Hungarian Academy of Sciences and University of Pannonia Budapest Hungary jr@post.tau.il Raphael Yuster Department of Mathematics University Haifa Haifa 31905 Israel raphy@math.haifa.ac.il 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 .
