Name
Abstract | ||
|---|---|---|
A path P in an edge-colored graph (not necessarily a proper edge-coloring) is a rainbow path if no two edges of P are colored the same. For an ℓ-connected graph G and an integer k with 1 ≤ k ≤ ℓ, the rainbow k-connectivity rck(G) of G is the minimum integer j for which there exists a j-edge-coloring of G such that every two distinct vertices of G are connected by k internally disjoint rainbow paths. The rainbow k-connectivity of the complete graph Kn is studied for various pairs k, n of integers. It is shown that for every integer k ≥ 2, there exists an integer f(k) such that rck(Kn) = 2 for every integer n ≥ f(k). We also investigate the rainbow k-connectivity of r-regular complete bipartite graphs for some pairs k,r of integers with 2 ≤ k ≤ r. It is shown that for each integer k ≥ 2, there exists an integer r such that rck(Kr,r) = 3. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009 |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1002/net.v54:2 | Networks |
Keywords | Field | DocType |
edge coloring | Integer,Edge coloring,Discrete mathematics,Complete graph,Combinatorics,Disjoint sets,Vertex (geometry),Bipartite graph,Regular graph,Connectivity,Mathematics | Journal |
Volume | Issue | ISSN |
54 | 2 | 0028-3045 |
Citations | PageRank | References |
33 | 5.59 | 0 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gary Chartrand | 1 | 199 | 32.05 |
| Garry L. Johns | 2 | 68 | 11.78 |
| Kathleen A. McKeon | 3 | 36 | 6.94 |
| Ping Zhang | 4 | 292 | 47.70 |