| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 418472 | Discrete Applied Mathematics | 2016 | 4 Pages |
Abstract
An edge-coloured connected graph GG is rainbow connected if each two vertices are connected by a path whose edges have distinct colours. If such a colouring uses kk colours then GG is called kk-rainbow connected. The rainbow connection number of GG, denoted by rc(G), is the minimum kk such that GG is kk-rainbow connected. Even the problem to decide whether rc(G)=2 is NP-complete. It has been shown that if GG is a connected graph of order nn and size mm with n−22+2≤m≤n−12, then 2≤rc(G)≤3.In this paper we will present sufficient conditions for graphs GG of this size to fulfil rc(G)=2 depending on vertex degrees.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Arnfried Kemnitz, Ingo Schiermeyer,