Note on Minimally d-Rainbow Connected Graphs |
| |
Authors: | Hengzhe Li Xueliang Li Yuefang Sun Yan Zhao |
| |
Institution: | 1. Center for Combinatorics and LPMC-TJKLC, Nankai University, Tianjin, 300071, China
|
| |
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}\) . |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|