Gracefulness of Some Arbitrary Supersubdivision of Cycle

Abstract

A labeling of a graph is a mapping that carries some set of graph elements into numbers (usually positive integers). Graceful labeling of a graph with \(q\) edges is an injection from the set of its vertices to the sequence \(\lbrace 0,1,2, \ldots, q\rbrace\) such that the values of edges are all integers from \(1\) to \(q\), the value of an edge being absolute value of the difference between the integers attributed to its end vertices. In 2009, Sethuraman [8] posed a problem of labeling of arbitrary supersubdivision of graph. Fact that all cycles are not graceful in general, it was intresting to study same for arbitrary supersubdivisions of cycles. This inspiration lead us to some good results. In this paper, we prove that Even arbitrary supersubdivision of cycle is graceful. We also prove that Odd arbitrary supersubdivision of cycle \(C_n\), for \(n\) even is graceful and for \(n\) odd is not graceful.