PDF
Discussiones Mathematicae Graph Theory 24(2) (2004)
345-353
DOI: https://doi.org/10.7151/dmgt.1235
CYCLIC DECOMPOSITIONS OF COMPLETE GRAPHS INTO SPANNING TREES
Dalibor Froncek
University of Minnesota Duluth
Department of Mathematics and Statistics
University of Minnesota Duluth
1117 University Dr., Duluth, MN 55812, U.S.A.
and
Technical University Ostrava
e-mail: dfroncek@d.umn.edu
Abstract
We examine decompositions of complete graphs with an even number of vertices, K2n, into n isomorphic spanning trees. While methods of such decompositions into symmetric trees have been known, we develop here a more general method based on a new type of vertex labelling, called flexible q-labelling. This labelling is a generalization of labellings introduced by Rosa and Eldergill.Keywords: graph factorization, graph labelling, spanning trees.
2000 Mathematics Subject Classification: 05C70, 05C78.
References
| [1] | J. Bosák, Decompositions of Graphs (Kluwer, Dordrecht, 1990). |
| [2] | P. Eldergill, Decompositions of the complete graph with an even number of vertices (M.Sc. thesis, McMaster University Hamilton, 1997). |
| [3] | D. Froncek and M. Kubesa, Factorizations of complete graphs into spanning trees, Congressus Numerantium 154 (2002) 125-134. |
| [4] | J.A. Gallian, A dynamic survey of graph labeling, Electronic Journal of Combinatorics DS6 (2001). |
| [5] | G. Ringel, Problem 25, in: Theory of Graphs and its Applications, (Proc. Symp. Smolenice 1963) ed., M. Fiedler (Academia, Prague, 1964) 162. |
| [6] | A. Rosa, Cyclic decompositions of complete graphs (Ph.D. thesis, Slovak Academy of Science, Bratislava, 1965). |
| [7] | 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. |
Received 26 November 2002
Revised 21 May 2003
Close