Vertex graceful labeling of some classes of graphs.

Authors

  • A. P. Santhakumaran Hindustan Institute of Technology and Science.
  • P. Balaganesan Hindustan Institute of Technology and Science.

Keywords:

Caterpillar, One vertex union graphs, Regular spider, Actinia graph, Vertex-graceful labeling, Strong vertex-graceful labeling

Abstract

A connected graph G = (V, E) of order atleast two, with order p and size q is called vertex-graceful if there exists a bijection f : V → {1, 2, 3, ··· p} such that the induced function f * : E → {0, 1, 2, ··· q - 1} defined by f * (uv) = (f(u) + f(v))(mod q) is a bijection. The bijection f is called a vertex-graceful labeling of G. A subset S of the set of natural numbers N is called consecutive if S consists of consecutive integers. For any set X, a mapping f : XN is said to be consecutive if f(X) is consecutive. A vertex-graceful labeling f is said to be strong if the function ƒ₁ : EN defined by ƒ₁(e) = f(u)+ f(v) for all edges e = uv in E forms a consecutive set. It is proved that one vertex union of odd number of copies of isomorphic caterpillars is vertex-graceful and any caterpillar is strong vertex-graceful. It is proved that a spider with even number of legs (paths) of equal length appended to each vertex of an odd cycle is vertex-graceful. It is also proved that the graph lA(mj , n) is vertex-graceful for both n and l odd, 0 ≤ in - 1, 1 ≤ jmi. Further, it is proved that the graph A(mj , n) is strong vertex-graceful for n odd, 0 ≤ i n - 1, 1 ≤ jmi.

Author Biographies

A. P. Santhakumaran, Hindustan Institute of Technology and Science.

Department of Mathematics.

 

P. Balaganesan, Hindustan Institute of Technology and Science.

Research Scholar, Department of Mathematics.

 

References

D. Acharya, S. Arumugam, and A. Rosa, Labeling of Discrete Structures and Applications, Narosa Publishing House, New Delhi, (2008).

P. Bahl, S. Lake, and A. Wertheim, Gracefulness of Families of Spiders, Involve, 3, pp. 241-247, (2010).

S. Bloom and D. F. Hsu, On graceful digraphs and a problem in network addressing, Congr. Numer., 35, pp. 91-103, (1982).

S. Bloom and D. F. Hsu, On graceful directed graphs that are computational models of some algebraic systems, Graph Theory with Applications to Algorithms and Computers, Ed. Y. Alavi, Wiley, New York, (1985).

G. Chartrand and P. Zhang, An Introduction to Graph Theory, Tata McGrawHill Edition, (2006).

J. A. Gallian, A Dynamic Survey of Graph Labeling, The Electronic. J. Combin., DS17, pp. 1-384, (2014).

S. W. Golomb, How to number a graph, Graph Theory and Computing, R. C.Read, ed., Academic Press, New York, pp. 23-37, (1972).

F. Harary, Graph Theory, Addison-Wesley, (1969).

F. Hsu and A. D. Keedwell, Generalized complete mappings, neofields, sequenceable groups and block designs, I, Pacific J. Math., 111, pp. 317-332, (1984).

F. Hsu and A. D. Keedwell, Generalized complete mappings, neofields, sequenceable groups and block designs, II, Pacific J. Math., 117, pp. 291-312, (1985).

J. Jeba Jesintha and G. Sethuraman, A new class of graceful rooted trees, J. Discrete Math. Sci. Cryptogr., 11, pp. 421-435, (2008).

A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs, Gordon and Breach, N. Y. and Dunod Paris, pp. 349-355, (1967).

P. Selvaraju, P. Balaganesan and J. Renuka, V. Balaji, On Vertex-graceful Labeling, Bulletin of Kerala Mathematics Association, 9, pp. 179-184, (2012).

P. Selvaraju, P. Balaganesan and J. Renuka, Vertex-graceful graph c2k∪ C2k+1, European Journal of Scientific and Research, 97, pp. 192-196, (2013).

P. Selvaraju, P. Balaganesan and J. Renuka, Vertex-graceful Labeling of Some Path Related Graphs, International J. Math. Combin., 3, pp. 44-49, (2013).

P. Selvaraju, P. Balaganesan and J. Renuka and M. L. Suresh, Vertex- graceful Labeling of Ci ∪ Cj ∪ Cl, Applied Mathematical Sciences, 8 (82), pp. 4047-4052, (2014).

P. Selvaraju, P. Balaganesan and J. Renuka and M. L. Suresh, Harmonious and Vertex-graceful Labeling of Path and Star Related Graphs, International Journal of Pure and Applied Mathematics, 93, pp. 501-509, (2014).

Sin-min Lee, Y. C. Pan and Ming Chen Tsai, On vertex-graceful graph (p, p + 1) - graphs, Congressus Numerantium 172, pp. 65-78, (2009).

W. C. Shiu, P. C. B. Lam, Super-edge-graceful labelings of multi-level wheel graphs, fan graphs and actinia graphs, Congressus Numerantium 174, pp. 49-63, (2005).

Published

2018-03-15

How to Cite

[1]
A. P. Santhakumaran and P. Balaganesan, “Vertex graceful labeling of some classes of graphs.”, Proyecciones (Antofagasta, On line), vol. 37, no. 1, pp. 19-43, Mar. 2018.

Issue

Section

Artículos

Most read articles by the same author(s)

1 2 > >>