Rainbow Connection in 3-Connected Graphs |
| |
| Authors: | Xueliang Li Yongtang Shi |
| |
| Affiliation: | 1. Center for Combinatorics and LPMC-TJKLC, Nankai University, Tianjin, 300071, People’s Republic of China
|
| |
| Abstract: | 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 rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. In this paper, we proved that rc(G) ≤ 3(n + 1)/5 for all 3-connected graphs. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
