Rainbow regular order of graphs
Zdzisław Skupień, Andrzej Żak · 2008
Assume that the vertex set of the complete graph Kt is Zt if t is odd and Zt−1 ∪{∞}otherwise, with convention that x + ∞ =2x. If the color of any edge xy is defined to be x + y then GKt stands for Kt together with the resulting edge coloring. Hence color classes are maximum matchings rotationally/cyclically generated if t is even/odd. A rainbow subgraph of GKt has all edges with distinct colors. Given a graph H, the optimization problem we deal with is to determine the rainbow regular order, ρ(H), which is the smallest possible t such that GKt contains a rainbow copy of H. We have determined ρ for cycles, wheels, complete bipartite graphs and some families of trees. We have also obtained an upper bound for ρ for all trees. Furthermore, we have contributed to a related problem by Hartman [Discrete Math. 62 (1986), 183–196], which is to determine rainbow subgraphs of all minimally edge colored copies of a graph G. We have solved this problem for cycles, wheels and complete bipartite graphs in case G is a complete graph. Relations between our version of modular sum labelings and the known labelings, especially harmonious and elegant ones, are presented.