On graceful chain graphs

Abstract

A function f is a graceful labeling of a graph G with n edges if f is an injection from the vertices of G to the set {0, 1, ...,n} such that, when each edge uv is assigned the label | f(u) - f(v)|, the resulting edge labels are distinct. Chain graphs are obtained by the concatenation of blocks. In this paper we show that the problem of finding graceful labelings of a chain graph can be reduced to the problem of finding suitable labelings of its blocks. Graceful labelings of those chain graphs whose blocks are isomorphic to the cycles C₆, C₈, and C₁₂ or the 3-cube Q ₃ are presented.