2020/01/06 by Ping Li, Xueliang Li, Li, Ping +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO #msc:05C15 #msc:05C40
paper · pdf · doi:10.48550/arxiv.2001.01419
22 pages
arxiv created 2020/01/06 · arxiv updated 2020/01/07
A path in an edge-colored graph is called a monochromatic path if all edges of the path have a same color. We call k paths P1,⋯,Pk rainbow monochromatic paths if every Pi is monochromatic and for any two i≠ j, Pi and Pj have different colors. An edge-coloring of a graph G is said to be a rainbow monochromatic k-edge-connection coloring (or RMCk-coloring for short) if every two distinct vertices of G are connected by at least k rainbow monochromatic paths. We use rmck(G) to denote the maximum number of colors that ensures G has an RMCk-coloring, and this number is called the rainbow monochromatic k-edge-connection number. We prove the existence of RMCk-colorings of graphs, and then give some bounds of rmck(G) and present some graphs whose rmck(G) reaches the lower bound. We also obtain the threshold function for rmck(G(n,p))≥ f(n), where \lfloor(n)/(2)\rfloor> k≥ 1.