On λ-fold Rosa-type Labelings of Bipartite Multigraphs

Abstract

© 2017 Elsevier B.V. It is known that for a given (simple) graph G with n edges, there exits a cyclic G-decomposition of K2n+1 if and only if G admits a ρ-labeling. It is also known that if G is bipartite and it admits an ordered ρ-labeling, then there exists a cyclic G-decomposition of K2nx+1 for every positive integer x. We extend these concepts to labelings of multigraphs through what we call λ-fold ρ-labelings and ordered λ-fold ρ-labelings. Let Kmλ denote the λ-fold complete graph of order m. We sho that if a subgraph G of K2n/λ+1λ has size n, there exits a cyclic G-decomposition of K2n/λ+1λ if and only if G admits a λ-fold ρ-labeling. If in addition G is bipartite and it admits an ordered λ-fold ρ-labeling, then there exists a cyclic G-decomposition of K2nx/λ+1λ for every positive integer x. We discuss some classes of graphs and multigraphs that admit such labelings.