Premium
The rainbow connectivity of a graph
Author(s) -
Chartrand Gary,
Johns Garry L.,
McKeon Kathleen A.,
Zhang Ping
Publication year - 2009
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20296
Subject(s) - combinatorics , rainbow , mathematics , integer (computer science) , graph , bipartite graph , connectivity , edge coloring , discrete mathematics , disjoint sets , path (computing) , graph power , line graph , physics , computer science , quantum mechanics , programming language
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 rc k ( 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 K n 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 rc k ( K n ) = 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 rc k ( K r , r ) = 3. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009