Cookies

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

Profile

Publication details for Professor Matthew Johnson

Hilton, A. J. W., Johnson, Matthew., Rodger, C. A. & Wantland, E. B. (2003). Amalgamations of connected k-factorizations. Journal of Combinatorial Theory Series B 88(2): 267-279.

Author(s) from Durham

Abstract

In this paper, necessary and sufficient conditions are found for a graph with exactly one amalgamated vertex to be the amalgamation of a k-factorization of Kkn+1 in which each k-factor is connected. From this result, necessary and sufficient conditions for a given edge-coloured Kt to be embedded in a connected k-factorization of Kkn+1 are deduced.

References

1

B. Alspach, H. Gavlas, Cycle decompositions of Kn and Kn  I; J. Combin. Theory B 81 (2001)
77–99.

2

L.D. Andersen, A.J.W. Hilton, Generalized latin rectangles II: embedding, Discrete Math. 31 (1980)
235–260.

3

L.D. Andersen, A.J.W. Hilton, E. Mendelsohn, Embedding partial Steiner triple systems, Proc.
London Math Soc. 41 (1980) 557–576.

4

J. Doyen, R.M. Wilson, Embeddings of Steiner triple systems, Discrete Math. 5 (1973) 229–239.

5

H. Hanani, On quadruple systems, Canad. J. Math. 12 (1960) 145–157.

6

A.J.W. Hilton, Hamiltonian decompositions of complete graphs, J. Combin. Theory B 36 (1984)
125–134.

7

A.J.W. Hilton, C.A. Rodger, Hamiltonian decompositions of complete regular s-partite graphs,
Discrete Math. 48 (1986) 63–78.

8

A.J.W. Hilton, C.A. Rodger, The embedding of partial triple systems when 4 divides l; J. Combin.
Theory A56 (1991) 109–137.

9

A. Johansson, A note on extending partial triple systems, submitted for publication.

10

Rev.T.P. Kirkman, On a problem in combinatorics, Cambridge Dublin Math. J. 2 (1847) 191–204.

11

C.C. Lindner, C.A. Rodger, Decompositions into cycles II: cycle systems, in: J. Dinitz, D. Stinson
(Eds.), Contemporary Design Theory: ACollectio n of Surveys, Wiley, New York, 1992.

12

C.C. Lindner, C.A. Rodger, A partial m ¼ ð2k þ 1Þ-cycle system of order n can be embedded in an mcycle
system of order ð2n þ 1Þm; Discrete Math. 117 (1993) 151–159.

13

C.C. Lindner, C.A. Rodger, Embedding directed and undirected partial cycle systems of index l;
J. Combin. Designs 1 (1993) 113–123.

14

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

15

C.St.J.A. Nash-Williams, Connected detachments of graphs and generalized Euler trails, J. London
Math. Soc. 31 (2) (1985) 17–29.

16

C.A. Rodger, E.B. Wantland, Embedding edge-colourings into 2-edge-connected k-factorizations of
Kknþ1; J. Graph Theory 19 (1995) 169–185.

17

M. Sajna, Cycle decompositions III: complete graphs and fixed length cycles, J. Combin. Designs 10
(2002) 27–78.

18

M. Tarsi, Decompositions of complete multigraphs into stars, Discrete Math. 26 (1979) 273–278.

19

M. Tarsi, Decomposition of the complete multigraph into simple paths: non-balanced handcuffed
designs, J. Combin. Theory A34 (1983) 60–70.

20

D. West, Introduction to Graph Theory, Prentice-Hall, Englewood Cliffs, NJ, 1996.