Menu
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 \(spc_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 \(spc_2(K_{r,s}) = \left\lceil ^{r-1}\sqrt{s} \right\rceil\) for 2 ≤ r ≤ s.