On λ-fold Rosa-type Labelings of Bipartite Multigraphs

• Main Authors: Bunge R., El-Zanati S., Mudrock J., Vanden Eynden C., Wannasit W.
• Format: Journal
• Published: 2017
• Online Access: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85021397534&origin=inward; http://cmuir.cmu.ac.th/jspui/handle/6653943832/40317
• Institution: Chiang Mai University

© 2017 Elsevier B.V. It is known that for a given (simple) graph G with n edges, there exits a cyclic G-decomposition of K 2n+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 K 2nx+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.