2018/10/28 by Ping Li, Xueliang Li, Li, Ping +1
Mathematics · #05C15 #05C40 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C15 #msc:05C40
paper · pdf · doi:10.48550/arxiv.1810.11820
16 pages
arxiv created 2018/10/28 · arxiv updated 2018/10/30
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 colored with a same color. We use mck(G) and umck(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, mck(G)=e(G)-e(H)+\lfloor(k)/(2)\rfloor, 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 when k≥4 is even, and for G=Kk,n when k≥4 is even, or when k=3 and n≥ k. When G is a minimal k-edge-connected graph, we give an upper bound of mck(G), i.e., mck(G)≤ k-1, and mck(G)≤ \lfloor(k)/(2)\rfloor when G=Kk,n. For the uniformly monochromatic k-edge-connectivity, we prove that for all k, umck(G)=e(G)-e(H)+1, where H is a minimum k-edge-connected spanning subgraph of G.