Note on Minimally d-Rainbow Connected Graphs

Autor: Yuefang Sun, Yan Zhao, Xueliang Li, Hengzhe Li
Rok vydání: 2013
Předmět:
Zdroj: Graphs and Combinatorics. 30:949-955
ISSN: 1435-5914
0911-0119
DOI: 10.1007/s00373-013-1309-9
Popis: An edge-colored graph G, where adjacent edges may have the same color, is rainbow connected if every two vertices of G are connected by a path whose edges have distinct colors. A graph G is d-rainbow connected if one can use d colors to make G rainbow connected. For integers n and d let t(n, d) denote the minimum size (number of edges) in d-rainbow connected graphs of order n. Schiermeyer got some exact values and upper bounds for t(n, d). However, he did not present a lower bound of t(n, d) for $${3 \leq d < \lceil\frac{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 \leq d < \lceil\frac{n}{2}\rceil}$$ .
Databáze: OpenAIRE
Externí odkaz: