Note on the Rainbow $k$-Connectivity of Regular Complete Bipartite Graphs

Details Note on the Rainbow $k$-Connectivity of Regular Complete Bipartite Graphs Note on the Rainbow $k$-Connectivity of Regular Complete Bipartite Graphs

2010-04-14

arxiv.org/abs/1004.2312v1

Mathematics

Combinatorics

6 pages

Scientific paper

A path in an edge-colored graph $G$, where adjacent edges may be colored the same, is called a rainbow path if no two edges of the path are colored the same. For a $\kappa$-connected graph $G$ and an integer $k$ with $1\leq k\leq \kappa$, the rainbow $k$-connectivity $rc_k(G)$ of $G$ is defined as the minimum integer $j$ for which there exists a $j$-edge-coloring of $G$ such that any two distinct vertices of $G$ are connected by $k$ internally disjoint rainbow paths. Denote by $K_{r,r}$ an $r$-regular complete bipartite graph. Chartrand et al. in "G. Chartrand, G.L. Johns, K.A. McKeon, P. Zhang, The rainbow connectivity of a graph, Networks 54(2009), 75-81" left an open question of determining an integer $g(k)$ for which the rainbow $k$-connectivity of $K_{r,r}$ is 3 for every integer $r\geq g(k)$. This short note is to solve this question by showing that $rc_k(K_{r,r})=3$ for every integer $r\geq 2k\lceil\frac{k}{2}\rceil$, where $k\geq 2$ is a positive integer.

Affiliated with

Also associated with

No associations

Rating

Note on the Rainbow $k$-Connectivity of Regular Complete Bipartite Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Note on the Rainbow $k$-Connectivity of Regular Complete Bipartite Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Note on the Rainbow $k$-Connectivity of Regular Complete Bipartite Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-525109