Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2025-01-05T12:03:00.842Z Has data issue: false hasContentIssue false

5 - Switching techniques for edge decompositions of graphs

Published online by Cambridge University Press:  21 July 2017

By
Daniel Horsley
Edited by
Anders Claesson ,
Mark Dukes ,
Sergey Kitaev ,
David Manlove  and
Kitty Meeks
Daniel Horsley
Affiliation:
Monash University
Anders Claesson
Affiliation:
University of Iceland, Reykjavik
Mark Dukes
Affiliation:
University College Dublin
Sergey Kitaev
Affiliation:
University of Strathclyde
David Manlove
Affiliation:
University of Glasgow
Kitty Meeks
Affiliation:
University of Glasgow
Get access

Summary

Abstract

This article concerns a class of techniques, herein referred to as edge switching techniques, that enable a new edge decomposition to be obtained from an existing one by interchanging edges between the subgraphs in the decomposition. These techniques can be viewed as generalisations of classical path switching methods for proper edge colourings. Their use in other edge decomposition settings dates back at least to 1980, but the last ten years have seen them rapidly developed and employed to resolve Lindner's conjecture on embedding partial Steiner triple systems, Alspach's cycle decomposition problem, and numerous other questions. Here we aim to give the reader a gentle introduction to these techniques and to some of their most significant applications beyond edge colouring.

Overview

An edge decomposition (hereafter simply a decomposition) of a graph G is a set of subgraphs of G such that each edge of G occurs in exactly one of the subgraphs. Questions concerning edge decompositions of graphs form a major theme in graph theory, combinatorial design theory, and finite geometry. Significantly for our purposes here, proper edge colourings of graphs are simply edge decompositions into matchings.

The edge switching techniques that we discuss here are methods that enable a new decomposition to be obtained from an existing one by interchanging edges between the graphs in the decomposition. They can be seen as an extension of the classical switching methods in graph colouring used by, for example, Kempe [66] and Vizing [92]. In 1980 Andersen, Hilton and Mendelsohn [4] employed a seminal example of edge switching in the setting of triangle decompositions. This result was eventually extended to 4- and 5-cycle decompositions by Raines and Szaniszló [81] in 1999 and again to decompositions into cycles of arbitrary lengths in 2005 [27]. Since then, edge switching techniques have been rapidly developed and applied to new settings and problems. This article aims to survey these techniques and some of their major applications beyond edge colouring.

Type
Chapter
Information
Surveys in Combinatorics 2017 , pp. 238 - 271
Publisher: Cambridge University Press
Print publication year: 2017

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] B., Alspach, Research Problem 3, Discrete Math. 36 1981, 333.
[2] B., Alspach and H., Gavlas, Cycle decompositions of Kn and Kn -I, J. Combin. Theory Ser. B 81 2001, 77–99.
[3] L.D., Andersen and A.J.W., Hilton, Generalized latin rectangles II: embedding, Discrete Math. 31 1980, 235–260.
[4] L.D., Andersen, A.J.W., Hilton and E., Mendelsohn, Embedding partial Steiner triple systems, Proc. London Math. Soc. 41 1980, 557–576.
[5] L.D., Andersen and C.A., Rodger, Decompositions of complete graphs: Embedding partial edge-colourings and the method of amalgamations, Surveys in Combinatorics, Lond. Math. Soc. Lect. Note Ser. 307 2003, 7–41.
[6] D., Archdeacon, M., Debowsky, J., Dinitz and H., Gavlas, Cycle systems in the complete bipartite graph minus a one-factor, Discrete Math. 284 2004, 37–43.
[7] J-C., Bermond, C., Huang and D., Sotteau, Balanced cycle and circuit designs: even cases, Ars Combin. 5 1978, 293–318.
[8] J.C., Bermond and D., Sotteau, Cycle and circuit designs odd case, Contributions to graph theory and its applications (Internat. Colloq., Oberhof, 1977) (German), pp. 11–32, Tech. Hochschule Ilmenau, Ilmenau, 1977.
[9] M.A., Bahmanian, Detachments of Hypergraphs I: The Berge- Johnson Problem, Combin. Probab. Comput. 21 2012, 483–495.
[10] A., Bahmanian and C., Rodger, Embedding factorizations for 3- uniform hypergraphs, J. Graph Theory 73 2013, 216–224.
[11] Z., Baranyai, On the factorization of the complete uniform hypergraph, Infinite and finite sets, Colloquia Math. Soc. János Bolyai 10 1973, 91–107.
[12] Z., Baranyai, The edge-coloring of complete hypergraphs I, J. Combin. Theory Ser. B 26 (1979),276–294.
[13] Z., Baranyai and A.E., Brouwer, Extension of colorings of the edges of a complete (uniform hyper)graph, Math. Centre Report ZW91 (Mathematisch Centrum Amsterdam). Zbl. 362.05059 (1977).
[14] B., Barber, D., Kühn, A., Lo and D., Osthus, Edge decompositions of graphs with high minimum degree, Advances in Mathematics 288 2016, 337–385.
[15] E.J., Billington, Multipartite graph decomposition: cycles and closed trails, Matematiche (Catania) 59 2004, 53–72.
[16] D., Bryant, Cycle decompositions of complete graphs, Surveys in Combinatorics, Lond. Math. Soc. Lect. Note Ser. 346 2007, 67–97.
[17] D., Bryant, A conjecture on small embeddings of partial Steiner triple systems, J. Combin. Des. 10 2002, 313–321.
[18] D., Bryant, Packing paths in complete graphs, J. Combin. Theory Ser. B, 100 2010, 206–215.
[19] D., Bryant, On almost-regular edge colourings of hypergraphs (preprint).
[20] D., Bryant, Embeddings of partial Steiner triple systems, J. Combin. Theory Ser. A 106 2004, 77–108.
[21] D., Bryant and M., Buchanan, Embedding partial totally symmetric quasigroups, J. Combin. Theory Ser. A 114 2007, 1046–1088.
[22] D.E., Bryant, D.G., Hoffman and C.A., Rodger, 5-cycle systems with holes, Des. Codes Cryptogr. 8 1996, 103–108.
[23] D., Bryant and D., Horsley, Steiner triple systems with two disjoint subsystems, J. Combin. Des. 14 2006, 14–24.
[24] D., Bryant and D., Horsley, A proof of Lindner's conjecture on embeddings of partial Steiner triple systems, J. Combin. Des. 17 2009, 63–89.
[25] D., Bryant and D., Horsley, Decompositions of complete graphs into long cycles, Bull. London Math. Soc. 41 2009, 927–934.
[26] D., Bryant and D., Horsley, An asymptotic solution to the cycle decomposition problem for complete graphs, J. Combin. Theory Ser. A 117 2010, 1258–1284.
[27] D., Bryant, D., Horsley and B., Maenhaut, Decompositions into 2-regular subgraphs and equitable partial cycle decompositions, J. Combin. Theory Ser. B 93 2005, 67–72.
[28] D., Bryant, D., Horsley, B., Maenhaut and B.R., Smith, Cycle decompositions of complete multigraphs, J. Combin. Des. 19 2011, 42–69.
[29] D., Bryant, D., Horsley, B., Maenhaut and B.R., Smith, Decompositions of complete multigraphs into cycles of varying lengths, arXiv preprint, arXiv:1508.00645.
[30] D., Bryant, D., Horsley and W., Pettersson, Cycle decompositions V: Complete graphs into cycles of arbitrary lengths, Proc. London Math. Soc. 108 2014, 1153–1192.
[31] D., Bryant and B., Maenhaut, Almost Regular Edge Colorings and Regular Decompositions of Complete Graphs, J. Combin. Des. 16 2013, 499–506.
[32] D., Bryant, B., Maenhaut, K., Quinn and B.S., Webb, Existence and embeddings of partial Steiner triple systems of order ten with cubic leaves, Discrete Math. 284 2004, 83–95.
[33] D., Bryant and G., Martin, Small embeddings for partial triple systems of odd index, J. Combin. Theory Ser. A 119 2012, 283–309.
[34] D.E., Bryant and C.A., Rodger, On the Doyen-Wilson theorem for m-cycle systems, J. Combin. Des. 2 1994, 253–271.
[35] D.E., Bryant and C.A., Rodger, The Doyen-Wilson theorem extended to 5-cycles, J. Combin. Theory Ser. A 68 1994, 218–225.
[36] D.E., Bryant, C.A., Rodger and E.R., Spicer, Embeddings of m-cycle systems and incomplete m-cycle systems: m⩽ 14, Discrete Math. 171 1997, 55–75.
[37] N.J., Cavenagh and E.J., Billington, Decomposition of complete multipartite graphs into cycles of even length, Graphs Combin. 16 2000, 49–65.
[38] C-C., Chou and C-M., Fu, Decomposition of Km,n into 4-cycles and 2t-cycles, J. Comb. Optim. 14 2007, 205–218.
[39]C-C., Chou, C-M., Fu and W-C., Huang, Decomposition of Km,n into short cycles, Discrete Math. 197/198 (1999), 195–203.
[40] C.J., Colbourn, Embedding partial Steiner triple systems is NPcomplete, J. Combin. Theory Ser. A 35 1983, 100–105.
[41] C.J., Colbourn, M.J., Colbourn and A., Rosa, Completing small partial triple systems, Discrete Math. 45 1983, 165–179.
[42] C.J., Colbourn and A., Rosa, Triple Systems, Clarendon Press, Oxford (1999).
[43] A., Cruse, On embedding incomplete symmetric latin squares, J. Combin. Theory Ser. A 16 1974, 18–27.
[44] R., Diestel, Graph Theory (4th edition), Springer, Heidelberg (2010).
[45] J., Doyen and R.M., Wilson, Embeddings of Steiner triple systems, Discrete Math. 5 1973, 229–239.
[46] H.E., Dudeney, Amusements in Mathematics, Nelson, Edinburgh (1917), reprinted by Dover Publications, New York (1959).
[47] V., Fack and B.D., McKay, A generalized switching method for combinatorial estimation, Australas. J. Combin. 39 2007, 141–154.
[48] M.N., Ferencak and A.J.W., Hilton, Outline and amalgamated triple systems of even index, Proc. London Math. Soc. 84 2002, 1–34.
[49] H., Hanani, The existence and construction of balanced incomplete block designs, Ann. Math. Statist. 32 1961, 361–386.
[50] R., Häggkvist and T., Hellgren, Extensions of edge-colourings in hypergraphs I, Combinatorics, Paul Erdʺos is eighty, Bolyai Soc. Math. Stud. (1993), 215–238.
[51] K., Heinrich, Path-decompositions, Matematiche (Catania) 47 1993, 241–258.
[52] P., Hell and A., Rosa, Graph decompositions, handcuffed prisoners and balanced P-designs, Discrete Math. 2 1972, 229–252.
[53] A.J.W., Hilton, Hamiltonian Decompositions of Complete Graphs, J. Combin. Theory Ser. B 36 1984, 125–134.
[54] A.J.W., Hilton and C.A., Rodger, The embedding of partial triple systems when 4 divides ƛ, J. Combin. Theory Ser. A 56 1991, 109–137.
[55] D.G., Hoffman, C.C., Lindner and C.A., Rodger, On the construction of odd cycle systems, J. Graph Theory 13 1989, 417–426.
[56] D., Horsley, Decomposing various graphs into short even-length cycles, Ann. Comb. 16 2012, 571–589.
[57] D., Horsley, Small Embeddings of Partial Steiner Triple Systems, J. Combin. Des. 22 2014, 343–365.
[58] D., Horsley, Embedding Partial Steiner Triple Systems with Few Triples, SIAM J. Discrete Math. 28 2014, 1199–1213.
[59] D., Horsley and R.A., Hoyte, Doyen-Wilson Results for Odd Length Cycle Systems, J. Combin. Des. 24 2016, 308–335.
[60] D., Horsley and R.A., Hoyte, Decomposing Ku+w -Ku into cycles of various lengths, arXiv preprint, arXiv:1603.03908.
[61] D., Horsley and D.A., Pike, Embedding partial odd-cycle systems in systems with orders in all admissible congruence classes, J. Combin. Des. 18 2010, 202–208.
[62] S.H.Y., Hung and N.S., Mendelsohn, Handcuffed designs, Aequationes Math. 11 1974, 256–266.
[63] C., Huang and A., Rosa, On the existence of balanced bipartite designs, Utilitas Math. 4 1973, 55–75.
[64] A., Johansson, A note on extending partial triple systems, University of Umea, Sweden, preprint (1997).
[65] P., Keevash, The existence of designs, arXiv preprint, arXiv:1401.3665.
[66] A.B., Kempe, On the geographical problem of the four colours, Amer. J. Math. 2 (1879), 193–200.
[67] T.P., Kirkman, On a problem in combinations, Cambridge and Dublin Math. J. 2 1847, 191–204.
[68] R., Laskar and B., Auerbach, On decomposition of r-partite graphs into edge-disjoint Hamilton circuits, Discrete Math. 14 1976, 265–268.
[69] J.F., Lawless, On the construction of handcuffed designs, J. Combin. Theory Ser. A 16 (1974) 76–86.
[70] J.F., Lawless, Further results concerning the existence of handcuffed designs, Aequationes Math. 11 (1974) 97–106.
[71] C.C., Lindner, A partial Steiner triple system of order n can be embedded in a Steiner triple system of order 6n+3, J. Combin. Theory Ser. A 18 1975, 349–351.
[72] C.C., Lindner and T., Evans, Finite embedding theorems for partial designs and algebras, SMS 56, Les Presses de l'Université de Montréal, (1977).
[73] C.C., Lindner and C.A., Rodger, A partial m = (2k+1)-cycle system of order n can be embedded in an m-cycle system of order (2n+1)m, Discrete Math. 117 1993, 151–159.
[74] E., Lucas, “Récreations Mathématiqués,” Vol II, Gauthier-Villars, Paris (1892).
[75] J., Ma, L., Pu and H., Shen, Cycle decompositions of Kn,n -I, SIAM J. Discrete Math. 20 2006, 603–609.
[76] G., Martin and T.A., McCourt, Small embeddings for partial 5-cycle systems, J. Combin. Des. 20 2012, 199–226.
[77] C.J.H., McDiarmid, The solution of a timetabling problem, J. Inst. Math. Appl. 9 1972, 23–34.
[78] E., Mendelsohn and A., Rosa, Embedding maximal packings of triples, Congr. Numer. 40 1983, 235–247.
[79] M.E., Raines, More on embedding partial totally symmetric quasigroups, Australas. J. Combin. 14 1996, 297–309.
[80] M.E., Raines and C.A., Rodger, Embedding partial extended triple systems and totally symmetric quasigroups, Discrete Math. 176 1997, 211–222.
[81] M., Raines and Z., Szaniszló, Equitable partial cycle systems, Australas. J. Combin. 19 1999, 149–156.
[82] C.A., Rodger and S.J., Stubbs, Embedding partial triple systems, J. Combin. Theory Ser. A 44 1987, 241–252.
[83] C.A., Rodger and S.J., Stubbs, Embedding partial triple systems (Erratum), J. Combin. Theory Ser. A 66 1994, 182–183.
[84] A., Rosa and C., Huang, Another class of balanced graph designs: balanced circuit designs, Discrete Math. 12 1975, 269–293.
[85] M. Šajna, Cycle decompositions III: complete graphs and fixed length cycles, J. Combin. Des. 10 2002, 27–78.
[86] J., Schönheim, On maximal systems of k-tuples, Studia Sci. Math. Hungar. 1 1966, 363–368.
[87] B.R., Smith, Cycle decompositions of complete multigraphs, J. Combin. Des. 18 2010, 85–93.
[88] D., Sotteau, Decomposition of Km,n (K* m,n) into cycles (circuits) of length 2k, J. Combin. Theory Ser. B 30 1981, 75–81.
[89] M., Tarsi, Decomposition of a complete multigraph into simple paths: Nonbalanced handcuffed designs, J. Combin. Theory Ser. A 34 1983, 60–70.
[90] A.G., Thomason, Hamiltonian cycles and uniquely edge colourable graphs, Ann. Discrete Math. 3 1978, 259–268.
[91] C., Treash, The completion of finite incomplete Steiner triple systems with applications to loop theory, J. Combin. Theory Ser. A 10 1971, 259–265.
[92] V.G., Vizing, On an estimate of the chromatic class of a p-graph, Diskret Analiz 3 1964, 25–30.

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×