Some Results on Rosa-type Labelings of Graphs

Abstract

Labelings that are used in graph decompositions are called Rosa-type labelings. The gamma-labeling of an almost-bipartite graph is a natural generalization of an alpha-labeling of a bipartite graph. It is known that if a bipartite graph G with m edges possesses an alpha-labeling or an almost-bipartite graph G with m edges possesses a gamma-labeling, then the complete graph K_{2mx+1} admits a cyclic G-decomposition. A variation of an alpha-labeling is introduced in this paper by allowing additional vertex labels and some conditions on edge labels and show that whenever a bipartite graph G admits such a labeling, then there exists a supergraph H of G such that H is almost-bipartite and H has a gamma-labeling.