Product rosy labeling of graphs

Dalibor Fronček

Discussiones Mathematicae Graph Theory, Tome 28 (2008), p. 431-439 / Harvested from The Polish Digital Mathematics Library

Résumé

In this paper we describe a natural extension of the well-known ρ-labeling of graphs (also known as rosy labeling). The labeling, called product rosy labeling, labels vertices with elements of products of additive groups. We illustrate the usefulness of this labeling by presenting a recursive construction of infinite families of trees decomposing complete graphs.

Détail

Publié le : 2008-01-01

Zbl 1173.05040

EUDML-ID : urn:eudml:doc:270192

Bibliographie

[000] [1] R.E.L. Aldred and B.D. McKay, Graceful and harmonious labellings of trees, Bull. Inst. Combin. Appl. 23 (1998) 69-72. | Zbl 0909.05040

[001] [2] P. Eldergill, Decompositions of the complete graph with an even number of vertices (M.Sc. thesis, McMaster University, Hamilton, 1997).

[002] [3] S. El-Zanati and C. Vanden Eynden, Factorizations of $K_{m,n}$ into spanning trees, Graphs Combin. 15 (1999) 287-293, doi: 10.1007/s003730050062. | Zbl 0935.05075

[003] [4] D. Fronček, Cyclic decompositions of complete graphs into spanning trees, Discuss. Math. Graph Theory 24 (2004) 345-353, doi: 10.7151/dmgt.1235. | Zbl 1060.05080

[004] [5] D. Fronček, Bi-cyclic decompositions of complete graphs into spanning trees, Discrete Math. 303 (2007) 1317-1322, doi: 10.1016/j.disc.2003.11.061. | Zbl 1118.05079

[005] [6] D. Fronček, P. Kovár, T. Kovárová and M. Kubesa, Factorizations of complete graphs into caterpillars of diameter 5, submitted for publication. | Zbl 1220.05098

[006] [7] D. Fronček and T. Kovárová, 2n-cyclic labelings of graphs, Ars Combin., accepted.

[007] [8] D. Fronček and M. Kubesa, Factorizations of complete graphs into spanning trees, Congr. Numer. 154 (2002) 125-134. | Zbl 1021.05083

[008] [9] J.A. Gallian, A dynamic survey of graph labeling, Electronic Journal of Combinatorics, DS6 (2007). | Zbl 0953.05067

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

[010] [11] P. Hrnciar and A. Haviar, All trees of diameter five are graceful, Discrete Math. 233 (2001) 133-150, doi: 10.1016/S0012-365X(00)00233-8. | Zbl 0986.05088

[011] [12] M. Kubesa, Factorizations of complete graphs into [n,r,s,2] -caterpillars of diameter 5 with maximum center, AKCE Int. J. Graphs Combin. 1 (2004) 135-147. | Zbl 1062.05121

[012] [13] M. Kubesa, Spanning tree factorizations of complete graphs, J. Combin. Math. Combin. Comput. 52 (2005) 33-49. | Zbl 1067.05059

[013] [14] M. Kubesa, Factorizations of complete graphs into [r,s,2,2] -caterpillars of diameter 5, J. Combin. Math. Combin. Comput. 54 (2005) 187-193. | Zbl 1080.05075

[014] [15] M. Kubesa, Graceful trees and factorizations of complete graphs into non-symmetric isomorphic trees, Util. Math. 68 (2005) 79-86. | Zbl 1106.05076

[015] [16] M. Kubesa, Trees with α-labelings and decompositions of complete graphs into non-symmetric isomorphic spanning trees, Discuss. Math. Graph Theory 25 (2005) 311-324, doi: 10.7151/dmgt.1284. | Zbl 1105.05056

[016] [17] M. Kubesa, Factorizations of complete graphs into [n,r,s,2] -caterpillars of diameter 5 with maximum end, AKCE Int. J. Graphs Combin. 3 (2006) 151-161. | Zbl 1120.05070

[017] [18] G. Ringel, Problem 25, Theory of Graphs and its Applications, Proceedings of the Symposium held in Smolenice in June 1963 (Prague, 1964) 162.

[018] [19] G. Ringel, A. Llado and O. Serra, Decomposition of complete bipartite graphs into trees, DMAT Research Report 11 (1996) Univ. Politecnica de Catalunya.

[019] [20] A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs (Intl. Symp. Rome 1966), Gordon and Breach, Dunod, Paris, 1967, 349-355.

[020] [21] S.L. Zhao, All trees of diameter four are graceful, Graph Theory and its Applications: East and West (Jinan, 1986), Ann. New York Acad. Sci., New York 576 (1989) 700-706.