On rainbow connection (Q1010776): Difference between revisions
From MaRDI portal
Created a new Item |
Set profile property. |
||
(3 intermediate revisions by 2 users not shown) | |||
Property / author | |||
Property / author: Arieh Lev / rank | |||
Property / author | |||
Property / author: Arieh Lev / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 01:53, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On rainbow connection |
scientific article |
Statements
On rainbow connection (English)
0 references
7 April 2009
0 references
Summary: 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 \(rc(G)\), is the smallest number of colors that are needed in order to make \(G\) rainbow connected. In this paper we prove several non-trivial upper bounds for \(rc(G)\), as well as determine sufficient conditions that guarantee \(rc(G)=2\). Among our results we prove that if \(G\) is a connected graph with \(n\) vertices and with minimum degree 3 then \(rc(G) < 5n/6\), and if the minimum degree is \(\delta\) then \(rc(G) \leq \frac{\ln \delta}{\delta}n(1+o_\delta(1))\). We also determine the threshold function for a random graph to have \(rc(G)=2\) and make several conjectures concerning the computational complexity of rainbow connection.
0 references