Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-23T14:12:58.624Z Has data issue: false hasContentIssue false
  • English
  • Français

Amalgamated Factorizations of Complete Graphs

Published online by Cambridge University Press:  12 September 2008

J. K. Dugdale  and
A. J. W. Hilton
J. K. Dugdale
Affiliation:
Department of Mathematics, West Virginia University, PO Box 6310, Morgantown WV 26506-6310, U.S.A.
A. J. W. Hilton
Affiliation:
Department of Mathematics, University of Reading, Whiteknights, PO Box 220, Reading RG6 2AX, U.K.
Get access Rights & Permissions [Opens in a new window]

Abstract

We give some sufficient conditions for an (S, U)-outline T-factorization of Kn to be an (S, U)-amalgamated T-factorization of Kn. We then apply these to give various necessary and sufficient conditions for edge coloured graphs G to have recoverable embeddings in T-factorized Kn's.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 3 , Issue 2 , June 1994 , pp. 215 - 232
Copyright
Copyright © Cambridge University Press 1994

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Andersen, L. D. and Hilton, A. J. W. (1980) Generalized latin rectangles I: construction and decomposition. Discrete Math. 31 125–152.CrossRefGoogle Scholar
[2]Andersen, L. D. and Hilton, A. J. W. (1980) Generalized latin rectangles II: embedding. Discrete Math. 31 235–260.CrossRefGoogle Scholar
[3]Andersen, L. D. and Hilton, A. J. W. (1979) Generalized latin rectangles. In: Graph Theory and Combinatorics, Research Notes in Mathematics. Pitman, London, 1–17.Google Scholar
[4]Chetwynd, A. G. and Hilton, A. J. W. (1991) Outline symmetric latin squares. Discrete Math. 97 101–117.CrossRefGoogle Scholar
[5]Cruse, A. B. (1974) On embedding incomplete symmetric latin squares. J. Combinatorial Theory, Ser. A 16 18–22.CrossRefGoogle Scholar
[6]Cruse, A. B. (1974) On extending incomplete latin rectangles. Proc. 5th Southeastern Conf. on Combinatorics, Graph Theory and Computing.Florida Atlantic University, Boca Raton,Florida, 333–348.Google Scholar
[7]Evans, T. (1960) Embedding incomplete latin squares. Amer. Math. Monthly 67 958–961.CrossRefGoogle Scholar
[8]Häggkvist, R. and Johanson, A. (to appear 1994) (1,2)-factorizations of general Eulerian nearly regular graphs. Combinatorics, Probability and Computing.CrossRefGoogle Scholar
[9]Hilton, A. J. W. (1980) The reconstruction of latin squares, with applications to school timetabling and to experimental design. Math. Programming Study 13 68–77.CrossRefGoogle Scholar
[10]Hilton, A. J. W. (1981) School timetables. In: Hansen, P. (ed.) Studies on graphs and Discrete Programming. North-Holland, Amsterdam, 177–188.CrossRefGoogle Scholar
[11]Hilton, A. J. W. (1982) Embedding incomplete latin rectangles. Ann. Discrete Math. 13 121–138.Google Scholar
[12]Hilton, A. J. W. (1987) Outlines of Latin squares. Ann. Discrete Math. 34 225–242.Google Scholar
[13]Hilton, A. J. W. (1984) Hamiltonian decompositions of complete graphs. J. Combinatorial Theory, Ser. B 36 125–134.CrossRefGoogle Scholar
[14]Hilton, A. J. W. and Rodger, C. A. (1986) Hamiltonian decompositions of complete regular s-partite graphs. Discrete Math. 58 63–78.CrossRefGoogle Scholar
[15]Hilton, A. J. W. and Wojciechowski, J. (1993) Weighted quasigroups. Surveys in Combinatorics. London Mathematical Society Lecture Note Series 187 137–171.Google Scholar
[16]Hilton, A. J. W. and Wojciechowski, J. (submitted) Simplex Algebras.Google Scholar
[17]McDiarmid, C. J. H. (1972) The solution of a time-tabling problem. J. Inst. Math. Applies. 9 23–34.CrossRefGoogle Scholar
[18]Nash-Williams, C. St J. A. (1986) Detachments of graphs and generalized Euler trials. In: Proc. 10th British Combinatorics Conf., Surveys in Combinatorics137–151.Google Scholar
[19]Nash-Williams, C. St J. A. (1987) Amalgamations of almost regular edge-colourings of simple graphs. J. Combinatorial Theory, Ser. B 43 322–342.CrossRefGoogle Scholar
[20]Petersen, J. (1891) Die Theorie der regulären Graphen. Acta Math. 15 193–220.CrossRefGoogle Scholar
[21]Rodger, C. A. and Wantland, E.(to appear) Embedding edge-colourings into m-edge-connected k-factorizations. Discrete Math.Google Scholar
[22]Ryser, H. J. (1951) A combinatorial theorem with an application to latin squares. Proc. Amer. Math. Soc. 2 550–552.CrossRefGoogle Scholar
[23]Vizing, V. G. (1960) On an estimate of the chromatic class of a p-graph (in Russian). Diskret. Analiz. 3 25–30.Google Scholar
[24]de Werra, D. (1971) Balanced schedules. INFOR 9 230–237.Google Scholar
[25]de Werra, D. (1975) A few remarks on chromatic scheduling. In: Roy, B. (ed.) Combinatorial Programming: Methods and Applications. Reidel, Dordrecht. 337–342.CrossRefGoogle Scholar