A Study of the Major Graph Labelings of Trees

Article type: Research Article

Authors: Krishnaa, Auparajita

Affiliations: Guest Faculty, B‐1, 101 Vaishali Apartments, Sector 4, Hiranmagri, Udaipur 313 002 India, e‐mail: [email protected]

Abstract: Tree is one of the most studied and practically useful classes of graphs and is the attention of a great number of studies. There is absence of generalized results for tree as a class and even for one kind of labeling as whole. Only specialized results exist limited to specific types of trees only. A number of conjectures stand being unsolved. Graham and Sloane (1980) conjectured trees to be Harmonious and Ringel‐Kotzig conjectured trees to be Graceful about three decades ago. Kotzig and Rosa (1970) ask the question whether all trees are Magic or not. No generalized result for Antimagic labeling is given for trees so far. This paper presents the methodologies to obtain the major labeling schemes for trees viz., Harmonious, Sequential, Felicitous, Graceful, Antimagic and found the trees to be not Magic except T(2,1), thus solving the said conjectures. These findings could also be useful for those working in fields where graphs serve as models.

Keywords: vertex labeling, edge labeling

Journal: Informatica, vol. 15, no. 4, pp. 515-524, 2004