We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Computer Science


Publication details for Professor Matthew Johnson

Johnson, M. (2007). Amalgamations of factorizations of complete graphs. Journal of Combinatorial Theory, Series B 97(4): 597-611.

Author(s) from Durham


Let t be a positive integer, and let K=(k1,…,kt) and L=(l1,…,lt) be collections of nonnegative integers. A (t,K,L)-factorization of a graph is a decomposition of the graph into factors F1,…,Ft such that Fi is ki-regular and li-edge-connected. In this paper, we apply the technique of amalgamations of graphs to study (t,K,L)-factorizations of complete graphs. In particular, we describe precisely when it is possible to embed a factorization of Km in a (t,K,L)-factorization of Kn.


L. D. Andersen and A. J. W. Hilton, Generalized latin
rectangles, in: R.~J.~Wilson (Ed.), {Research Notes in
Mathematics}, Vol 34, Pitman, New York (1979), 1-17.

L. D. Andersen and A. J. W. Hilton, Generalized latin rectangles
II: Embedding, { Discrete Math.} {\bf 31} (1980) 235-260.

H. L. Buchanan, Graph factors and Hamiltonian decompositions, Ph.D
dissertation, West Virginia University (1997).

A. J. W. Hilton, Hamiltonian decompositions of complete graphs,
{ J. Combin. Theory Ser. B} {\bf 36} (1984) 125-134.

A.J.W. Hilton and M. Johnson, An algorithm for finding factorizations
of complete graphs, Journal of Graph Theory {\bf 43} (2003)

A. J. W. Hilton, M. Johnson, C. A. Rodger and E. B. Wantland,
Amalgamations of connected $k$-factorizations, J. Combin. Theory
Ser. B {\bf 88} (2003) 267-279.

A. J. W. Hilton and C. A. Rodger, Hamiltonian decompositions
of complete regular $s$-partite graphs, {Discrete Math.} {\bf 48}
(1986) 63-78.

W. R. Johnstone, Decompositions of complete graphs, { Bull.
London Math. Soc.} {\bf 32} (2000) 141-145.

C. St. J. A. Nash-Williams, Amalgamations of almost regular
edge-colourings of simple graphs, { J. Combin. Theory Ser. B} {\bf
43} (1987) 322-342.

C. St. J. A. Nash-Williams, Connected detachments of graphs and
generalized Euler trails, { J. London Math. Soc.} {\bf 31} (1985)

C. A. Rodger and E. B. Wantland, Embedding edge-colorings into
2-edge-connected $k$-factorizations of $K_{kn+1}$, { J. Graph
Theory} {\bf 10} (1995) 169-185.