2012/03/14 by Hengzhe Li, Xueliang Li, Li, Hengzhe +5
Computer Science · Mathematics · #05C15 #05C35 #05C40 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO #msc:05C15 #msc:05C35 #msc:05C40
paper · pdf · doi:10.48550/arxiv.1203.3030
8 pages
arxiv created 2012/03/14 · openalex publication_date 2012/03/14 · arxiv updated 2012/03/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An edge-colored graph G, where adjacent edges may have the same color, is \it rainbow connected if every two vertices of G are connected by a path whose edge has distinct colors. A graph G is \it k-rainbow connected if one can use k colors to make G rainbow connected. For integers n and d let t(n,d) denote the minimum size (number of edges) in k-rainbow connected graphs of order n. Schiermeyer got some exact values and upper bounds for t(n,d). However, he did not get a lower bound of t(n,d) for 3≤ d<\lceil(n)/(2)\rceil . In this paper, we improve his lower bound of t(n,2), and get a lower bound of t(n,d) for 3≤ d<\lceil(n)/(2)\rceil.