关于稀疏图彩虹连通数的注记

Note That on the Rainbow Connection Number of Dense Graphs

一个边染色图G称为彩虹连通图如果图G中任意两个点有一条边染不同颜色的路相连．连通图G的彩虹连通数是使图G彩虹连通需要的最小颜色数，记为rc（G）．我们依据Caro和Chakrabortyet等人的思想，研究了稀疏图的彩虹连通数，并得到了一些推广性的结果．我们证明了对于k≥2且G是一个阶为n有最小度σ（G）≥n/2-1＋logk n或最小度和σ2（G）≥n-2＋2logk n的非完全图，那么rc（G）≤k．我们也研究了非完全偶图中rc（G）≤k的邻域条件，以及直径为2的图中rc（C）≤k的最小度条件．

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 by re（G）, is the smallest number of colors that are needed to make G rainbow connected. Following the ideas of Caro and Chakrabortyet al., in this paper we also investigate the rainbow connection number of dense graphs, and get some generalized results. We show that for k 〉 2, if G is a non-complete graph of order n with minimum degree δ（G） ≥ n/2 - 1 ＋ logkn, or minimum degree-sum σ2（G） ≥ n - 2 ＋ 21ogkn, then re（G） ≤ k. We also consider the condition of neighbor with re（G） ≤ k in the non-complete bipartite graph, and the minimum degree condition in the graph of diameter 2.