Gracefulness of Some Arbitrary Supersubdivision of Cycle

Ujwala Deshmukh, Smita Amogh Bhatavadekar

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.

Keywords


Cycle; Subdivision of graphs; Supersubdivision of graphs; Arbitrary supersubdivision of a graph; Graceful labeling

Full Text:

PDF

References


R. Cattell, Graceful labeling of path, Discrete Math. 307 (2007), 3161 – 3176, DOI: 10.1016/j.disc.2007.03.046.

J. Gallian, A dynamic survey of graph labeling, The Electronic Journal of Combinatorics 18 (2011), #DS6, 1 – 502, https://www.combinatorics.org/files/Surveys/ds6/ds6v14-2011.pdf.

K. M. Kathiresan and S. Amutha, Arbitrary supersubdivision of stars are graceful, Indian J. Pure and Appl. Math. 35 (2004), 81 – 84.

K. M. Kathiresan, Subdivision of ladders are graceful, Indian Journal of Pure Appl Math. 23 (1) (1992), 21 – 23.

A. Kotzig, Recent and open problems in graceful graphs, in Proc. 15th Southeast. Conf. on Combinatorics, Graph Theory and Computing, 1984 (Baton Rouge, LA), Congr. Number 44, 197 – 219.

V. Ramchandran and C. Sekar, Graceful labeling of supersubdivision of ladder, Int. J. Maths & Its Appl. 2(2) (2014), 29 – 36, http://ijmaa.in/papers/2204.pdf.

A. Rosa, On certain valuations of the vertices of a graph, in Theory of Graphs, International Symposium, Rome, July 1966, pp. 349 – 355, Gordon and Breach, New York, USA (1967).

G. Sethuraman and P. Selvaraju, Gracefulness of supersubdivision of graphs, Indian Journal of Pure and Appl. Math. 32(7) (2001), 1059 – 1064.




DOI: http://dx.doi.org/10.26713%2Fjims.v10i4.870

eISSN 0975-5748; pISSN 0974-875X