Gracefulness of Some Arbitrary Supersubdivision of Cycle

Authors

  • Ujwala Deshmukh Department of Mathematics, Mithibai College (University of Mumbai) Vile Parle (West), Mumbai 400056
  • Smita Amogh Bhatavadekar Department of Applied Mathematics, Lokmanya Tilak College of Engineering (University of Mumbai), Mumbai 400709

DOI:

https://doi.org/10.26713/jims.v10i4.870

Keywords:

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

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.

Downloads

Download data is not yet available.

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.

Downloads

Published

2018-12-31
CITATION

How to Cite

Deshmukh, U., & Bhatavadekar, S. A. (2018). Gracefulness of Some Arbitrary Supersubdivision of Cycle. Journal of Informatics and Mathematical Sciences, 10(4), 599–611. https://doi.org/10.26713/jims.v10i4.870

Issue

Section

Research Articles