Minimal Equitability of Hairy Cycles

Abstract

Every labeling of the vertices of a graph with distinct natural numbers induces a natural labeling of its edges: the label of an edge \( (x,y) \) is the absolute value of the difference of the labels of \( x \) and \( y \). By analogy with graceful labelings, we say that a labeling of the vertices of a graph of order \( n \) is minimally \( k \)-equitable if the vertices are labelled with \( 1, 2, \ldots, n \) and in the induced labeling of its edges every label either occurs exactly \( k \) times or does not occur at all. For \( m \geq 3 \), let \( C_m’ \) (denoted also in the literature by \( C_m \circ K_1 \) and called a corona graph) be a graph with \( 2m \) vertices such that there is a partition of them into sets \( U \) and \( V \) of cardinality \( m \), with the property that \( U \) spans a cycle, \( V \) is independent and the edges joining \( U \) to \( V \) form a matching. Let \( \mathcal{P} \) be the set of all pairs \( (m, k) \) of positive integers such that \( k \) is a proper divisor of \( 2m \) (i.e., a divisor different from \( 2m \) and \( 1 \)) and \( k \) is odd if \( m \) is odd. We show that \( C_m’ \) is minimally \( k \)-equitable if and only if \( (m,k) \in \mathcal{P} \).