论文标题
彩虹单色$ k $ - 图形的连接着色
Rainbow monochromatic $k$-edge-connection colorings of graphs
论文作者
论文摘要
如果路径的所有边缘具有相同的颜色，则边缘色图中的路径称为单色路径。我们称$ k $路径$ p_1，\ cdots，p_k $ rainbow单色路径，如果每个$ p_i $都是单色$，则对于任何两个$ i \ neq j $，$ p_i $，$ p_j $和$ p_j $都有不同的颜色。图$ g $的边缘颜色据说是彩虹单色$ k $ - 连接着色（或$ rmc_k $ - 简短的颜色），如果每两个不同的$ g $的顶点与至少由$ k $ rainbor linbow nouthosic paths连接。我们使用$ rmc_k（g）$来表示确保$ g $具有$ rmc_k $ - 彩色的最大颜色数量，并且此数字称为彩虹单色$ k $ - edge-gedge-enctionnection。我们证明存在$ rmc_k $ - 图形的颜色，然后给出$ rmc_k（g）$的一些范围，并提供了一些图形，其$ rmc_k（g）$达到下限。我们还获得了$ rmc_k（g（n，p））\ geq f（n）$的阈值函数，其中$ \ lfloor \ frac {n} {2} {2} \ rfloor> k \ geq 1 $。
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 $P_1,\cdots,P_k$ rainbow monochromatic paths if every $P_i$ is monochromatic and for any two $i\neq j$, $P_i$ and $P_j$ have different colors. An edge-coloring of a graph $G$ is said to be a rainbow monochromatic $k$-edge-connection coloring (or $RMC_k$-coloring for short) if every two distinct vertices of $G$ are connected by at least $k$ rainbow monochromatic paths. We use $rmc_k(G)$ to denote the maximum number of colors that ensures $G$ has an $RMC_k$-coloring, and this number is called the rainbow monochromatic $k$-edge-connection number. We prove the existence of $RMC_k$-colorings of graphs, and then give some bounds of $rmc_k(G)$ and present some graphs whose $rmc_k(G)$ reaches the lower bound. We also obtain the threshold function for $rmc_k(G(n,p))\geq f(n)$, where $\lfloor\frac{n}{2}\rfloor> k\geq 1$.
