On labeling 2-regular graphs where the number of odd components is at most 2

Abstract

Several graph labelings were introduced by Rosa in 1967 as means of attacking graph decomposition problems. The most basic of these labelings is what is known as a ρ-labeling. Rosa showed that a graph G of size n admits a ρ-labeling if and only if there is a cyclic G-decomposition of K2n+i-He also showed that if G is bipartite and admits what is known as an a-labeling, then there exists a cyclic G-decomposition of K2xn+1 for all positive integers x. Here we show that the vertex-disjoint union of a graph that admits a modified ρ-labeling and any number of graphs that admit α-labelings has a ρ-labeling. We use this to also show that if the number of odd components in a 2-regular graph G is at most two, then G admits a ρ-labeling. This provides further evidence in support of a conjecture that every 2-regular graph admits a ρ-labeling.