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,\dots ,n$ and in the induced labeling of its edges every label either occurs exactly $k$ times or does not occur at all. For $m\ge 3$, let $C_m^{\prime }$ (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^{\prime }$ is minimally $k$-equitable if and only if $(m,k)\in \mathcal{P}$.