We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Note on Minimally d-Rainbow Connected Graphs.
- Authors
Li, Hengzhe; Li, Xueliang; Sun, Yuefang; Zhao, Yan
- Abstract
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}$$ .
- Subjects
GRAPH connectivity; GRAPH coloring; INTEGERS; GRAPH theory; MATHEMATICAL bounds; MATHEMATICAL analysis
- Publication
Graphs & Combinatorics, 2014, Vol 30, Issue 4, p949
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-013-1309-9