zbMATH — the first resource for mathematics

Tight super-edge-graceful labelings of trees and their applications. (English) Zbl 1346.05250
Summary: The concept of graceful labeling of graphs has been extensively studied. J. Mitchem and A. Simoson [Ars Comb. 37, 97–111 (1994; Zbl 0805.05074)] introduced a stronger concept called super-edge-graceful labeling for some classes of graphs. Among many other interesting pioneering results, J. Mitchem and A. Simoson [loc. cit.] provided a simple but powerful recursive way of constructing super-edge-graceful trees of odd order. In this note, we present a stronger concept of “tight” super-edge-graceful labeling. Such a super-edge graceful labeling has an additional constraint on the edge and vertices with the largest and smallest labels. This concept enables us to recursively construct tight super-edge-graceful trees of any order. As applications, we provide insights on the characterization of super-edge-graceful trees of diameter 4, a question posed by P. T. Chung et al. [Congr. Numerantium 181, 5–17 (2006; Zbl 1119.05095)]. We also observe infinite families of super-edge-graceful trees that can be generated from tight labelings. Given the direct applications of “tight” super-edge-graceful labeling to the study of super-edge-graceful labelings, we note that it is worthwhile to further examine recursively generated tight super-edge-graceful trees.
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C05 Trees
Full Text: DOI
[1] Lo, S. P., On edge-graceful labellings of graphs, Congr. Numer., 50, 231-241, (1985)
[2] Cabannis, S.; Michem, J.; Low, R., On edge-graceful regular graphs and trees, Ars Combin., 34, 129-142, (1992) · Zbl 0774.05085
[3] Lee, S. M.; Nowak, K.; Wang, L.; Wei, W., On the edge-graceful trees conjecture, J. Combin. Math. Combin. Comput., (2015), in press
[4] Mitchem, J.; Simoson, A., On edge-graceful and super-edge-graceful graphs, Ars Combin., 37, 97-111, (1994) · Zbl 0805.05074
[5] Simoson, A., Edge-graceful cootie, Congr. Numer., 101, 117-128, (1994) · Zbl 0837.05103
[6] Small, D., Regular (even) spider graphs are edge-graceful, Congr. Numer., 74, 247-254, (1990) · Zbl 0701.05048
[7] Lee, S. M., A conjecture on edge-graceful trees, Sci. Ser. A., 3, 45-57, (1989) · Zbl 0741.05025
[8] Gallian, J. A., A dynamic survey of graph labeling, Electron. J. Combin., (2014)
[9] Chuang, P. T.; Lee, S. M.; Gao, W. Y.; Schaffer, K., On the super edge graceful trees of even orders, Congr. Numer., 181, 5-17, (2006) · Zbl 1119.05095
[10] Lee, S. M.; Ho, Y. S., All trees of odd order with three even vertices are super edge-graceful, J. Combin. Math. Combin. Comput., 62, 53-64, (2007) · Zbl 1137.05064
[11] E. Krop, F. Mutiso, C. Raridan, On super edge-graceful trees of diameter four, preprint. · Zbl 1247.05208
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.