Vertex graceful labeling of some classes of graphs.
Keywords:
Caterpillar, One vertex union graphs, Regular spider, Actinia graph, Vertexgraceful labeling, Strong vertexgraceful labelingAbstract
A connected graph G = (V, E) of order atleast two, with order p and size q is called vertexgraceful 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 vertexgraceful 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 : X → N is said to be consecutive if f(X) is consecutive. A vertexgraceful labeling f is said to be strong if the function ƒ₁ : E → N 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 vertexgraceful and any caterpillar is strong vertexgraceful. It is proved that a spider with even number of legs (paths) of equal length appended to each vertex of an odd cycle is vertexgraceful. It is also proved that the graph lA(m_{j} , n) is vertexgraceful for both n and l odd, 0 ≤ i ≤ n  1, 1 ≤ j ≤ m_{i}. Further, it is proved that the graph A(m_{j} , n) is strong vertexgraceful for n odd, 0 ≤ i ≤ n  1, 1 ≤ j ≤ m_{i}.
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. 241247, (2010).
S. Bloom and D. F. Hsu, On graceful digraphs and a problem in network addressing, Congr. Numer., 35, pp. 91103, (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. 1384, (2014).
S. W. Golomb, How to number a graph, Graph Theory and Computing, R. C.Read, ed., Academic Press, New York, pp. 2337, (1972).
F. Harary, Graph Theory, AddisonWesley, (1969).
F. Hsu and A. D. Keedwell, Generalized complete mappings, neofields, sequenceable groups and block designs, I, Pacific J. Math., 111, pp. 317332, (1984).
F. Hsu and A. D. Keedwell, Generalized complete mappings, neofields, sequenceable groups and block designs, II, Pacific J. Math., 117, pp. 291312, (1985).
J. Jeba Jesintha and G. Sethuraman, A new class of graceful rooted trees, J. Discrete Math. Sci. Cryptogr., 11, pp. 421435, (2008).
A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs, Gordon and Breach, N. Y. and Dunod Paris, pp. 349355, (1967).
P. Selvaraju, P. Balaganesan and J. Renuka, V. Balaji, On Vertexgraceful Labeling, Bulletin of Kerala Mathematics Association, 9, pp. 179184, (2012).
P. Selvaraju, P. Balaganesan and J. Renuka, Vertexgraceful graph c2k∪ C2k+1, European Journal of Scientific and Research, 97, pp. 192196, (2013).
P. Selvaraju, P. Balaganesan and J. Renuka, Vertexgraceful Labeling of Some Path Related Graphs, International J. Math. Combin., 3, pp. 4449, (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. 40474052, (2014).
P. Selvaraju, P. Balaganesan and J. Renuka and M. L. Suresh, Harmonious and Vertexgraceful Labeling of Path and Star Related Graphs, International Journal of Pure and Applied Mathematics, 93, pp. 501509, (2014).
Sinmin Lee, Y. C. Pan and Ming Chen Tsai, On vertexgraceful graph (p, p + 1)  graphs, Congressus Numerantium 172, pp. 6578, (2009).
W. C. Shiu, P. C. B. Lam, Superedgegraceful labelings of multilevel wheel graphs, fan graphs and actinia graphs, Congressus Numerantium 174, pp. 4963, (2005).
Published
How to Cite
Issue
Section

Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
 No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.