Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Rainbow Connection Numbers for Undirected Double-Loop Networks
verfasst von : Yuefang Sun
Erschienen in: Advances in Global Optimization
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 investigate rainbow connection numbers of three subfamilies of undirected double-loop networks, denoted by rc(G(n; ±s
1, ±s
2)), where 1 ≤ s
1 < s
2 < n∕2. We almost determine the precise value for the case that \(s_{1} = 1,s_{2} = 2\). For the case that \(n = ks,s_{1} = 1,s_{2} = s\), where s ≥ 3 and k ≥ 1 are integers, we derive that \(rc(G(ks;\pm 1,\pm s)) \leq \min \{\lceil \frac{k} {2} \rceil + s,\lceil \frac{s+1} {2} \rceil + k - 1\}\). For the case that \(n = 2ks,s_{1} = 2,s_{2} = s\), where k ≥ 1 are integers and s ≥ 3 are odd integers, we have \(rc(G(n;\pm s_{1},\pm s_{2})) \leq \lceil \frac{ks} {2} \rceil + k\).