DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 24(2) (2004) 345-353
DOI: 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