Equitable Labellings of Cycles
Jerzy Wojciechowski · 1993
Abstract. Every labelling of the vertices of a graph with distinct natural numbers induces a natural labelling 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 labellings, we say that a labelling of the vertices of a graph of order n is minimally k-equitable if the vertices are labelled with 1, 2,..., n and in the induced labelling of its edges every label either occurs exactly k times or does not occur at all. Bloom [3] posed the following question: Is the condition that k is a proper divisor of n sufficient for the cycle Cn to have a minimal k-equitable labelling? We give a positive answer to this question. 1 1.