Monochromatic k-edge-connection colorings of graphs

摘要

A path in an edge-colored graph G is called monochromatic if any two edges on the path have the same color. For k >= 2, an edge-colored graph G is said to be monochromatic k-edge-connected if every two distinct vertices of G are connected by at least k edge-disjoint monochromatic paths, and G is said to be uniformly monochromatic k-edge-connected if every two distinct vertices are connected by at least k edge-disjoint monochromatic paths such that all edges of these k paths are colored with a same color. We use mc(k)(G) and umc(k)(G) to denote the maximum number of colors that ensures G to be monochromatic k-edge-connected and, respectively, G to be uniformly monochromatic k-edge-connected. In this paper, we first conjecture that for any k-edge-connected graph G, mc(k)(G) = e(G) - e(H)+[k/2], where H is a minimum k-edge-connected spanning subgraph of G. We verify the conjecture for k = 2. We also prove the conjecture for G = Kk+1 and G = K-k,K-n with n >= k >= 3. When G is a minimal k-edge-connected graph, we give an upper bound of mc(k)(G), i.e., mc(k)(G) <= k-1. For the uniformly monochromatic k-edge-connectivity, we prove that for all k, umc(k)(G) = e(G) - e(H) + 1, where H is a minimum k-edge-connected spanning subgraph of G. (C) 2019 Elsevier B.V. All rights reserved.