Strong Chromatic Connectivity of Complete Bipartite Graphs

Abstract

Let G be an edge-colored connected graph. For vertices u and v of G, a shortest u – v path P in G is a u – u geodesic and P is a proper u – u geodesic if no two adjacent edges in P are colored the same. An edge coloring of a connected graph G is called a proper k-geodesic coloring of G for some positive integer k if for every two nonadjacent vertices u and v of G, there exist at least k internally disjoint proper u – u geodesics in G. The minimum number of the colors required in a proper k-geodesic coloring of G is the strong proper k-connectivity $sp{c}_k(G)$ of G. Sharp lower bounds are established for the strong proper k-connectivity of complete bipartite graphs $K_{r,s}$ for all integers k, r, s with 2 ≤ k ≤ r ≤ s and it is shown that the strong proper 2-connectivity of $K_{r,s}$ is $sp{c}_2(K_{r,s})=\lceil {}^{r-1}\sqrt{s}\rceil$ for 2 ≤ r ≤ s.