{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:22:00Z","timestamp":1740122520848,"version":"3.37.3"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2024,10,3]],"date-time":"2024-10-03T00:00:00Z","timestamp":1727913600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,10,3]],"date-time":"2024-10-03T00:00:00Z","timestamp":1727913600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"ARC discovery Grant","award":["DP200100080"],"award-info":[{"award-number":["DP200100080"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Des. Codes Cryptogr."],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>An <jats:italic>H<\/jats:italic>-decomposition of a graph <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Gamma $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u0393<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is a partition of its edge set into subgraphs isomorphic to <jats:italic>H<\/jats:italic>. A transitive decomposition is a special kind of <jats:italic>H<\/jats:italic>-decomposition that is highly symmetrical in the sense that the subgraphs (copies of <jats:italic>H<\/jats:italic>) are preserved and transitively permuted by a group of automorphisms of <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Gamma $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u0393<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This paper concerns transitive <jats:italic>H<\/jats:italic>-decompositions of the graph <jats:inline-formula><jats:alternatives><jats:tex-math>$$K_n \\Box K_n$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mi>K<\/mml:mi>\n                      <mml:mi>n<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mo>\u25a1<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>K<\/mml:mi>\n                      <mml:mi>n<\/mml:mi>\n                    <\/mml:msub>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> where <jats:italic>H<\/jats:italic> is a path. When <jats:italic>n<\/jats:italic> is an odd prime, we present a construction for a transitive path decomposition where the paths in the decomposition are considerably large compared to the number of vertices. Our main result supports well-known Gallai\u2019s conjecture and an extended version of Ringel\u2019s conjecture.\n<\/jats:p>","DOI":"10.1007\/s10623-024-01493-9","type":"journal-article","created":{"date-parts":[[2024,10,3]],"date-time":"2024-10-03T10:02:07Z","timestamp":1727949727000},"page":"4231-4245","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Transitive path decompositions of Cartesian products of complete graphs"],"prefix":"10.1007","volume":"92","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2404-0344","authenticated-orcid":false,"given":"Ajani","family":"De Vas Gunasekara","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alice","family":"Devillers","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,10,3]]},"reference":[{"issue":"3","key":"1493_CR1","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1017\/S0004972700041101","volume":"10","author":"BR Alspach","year":"1974","unstructured":"Alspach B.R., Pullman N.J.: Path decompositions of digraphs. Bull. Aust. Math. Soc. 10(3), 421\u2013427 (1974).","journal-title":"Bull. Aust. Math. Soc."},{"key":"1493_CR2","doi-asserted-by":"crossref","unstructured":"Anshelevich E., Zhang L.: Path decomposition under a new cost measure with applications to optical network design. In: Lecture Notes in Comput. Sci., vol. 3221. Springer, Berlin (2004).","DOI":"10.1007\/978-3-540-30140-0_5"},{"issue":"5","key":"1493_CR3","doi-asserted-by":"publisher","first-page":"1293","DOI":"10.1016\/j.disc.2019.01.005","volume":"342","author":"M Bonamy","year":"2019","unstructured":"Bonamy M., Perrett T.J.: Gallai\u2019s path decomposition conjecture for graphs of small maximum degree. Discret. Math. 342(5), 1293\u20131299 (2019).","journal-title":"Discret. Math."},{"issue":"1","key":"1493_CR4","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/s00373-020-02251-z","volume":"37","author":"Y Chu","year":"2021","unstructured":"Chu Y., Fan G., Zhou C.: Decompositions of 6-regular bipartite graphs into paths of length six. Graphs Combin. 37(1), 263\u2013269 (2021).","journal-title":"Graphs Combin."},{"key":"1493_CR5","doi-asserted-by":"publisher","unstructured":"De Vas Gunasekara A.: Completion and embedding problems for combinatorial designs. Thesis, Monash University (2022). https:\/\/doi.org\/10.26180\/20444115.v1.","DOI":"10.26180\/20444115.v1"},{"issue":"3","key":"1493_CR6","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1112\/plms.12480","volume":"126","author":"A Gir\u00e3o","year":"2023","unstructured":"Gir\u00e3o A., Granet B., K\u00fchn D., Lo A., Osthus D.: Path decompositions of tournaments. Proc. Lond. Math. Soc. 126(3), 429\u2013517 (2023).","journal-title":"Proc. Lond. Math. Soc."},{"key":"1493_CR7","first-page":"115","volume":"141","author":"R H\u00e4ggkvist","year":"1989","unstructured":"H\u00e4ggkvist R.: Decompositions of complete bipartite graphs. Lond. Math. Soc. Lect. Notes Ser. 141, 115\u2013147 (1989).","journal-title":"Lond. Math. Soc. Lect. Notes Ser."},{"key":"1493_CR8","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/0012-365X(72)90005-2","volume":"2","author":"P Hell","year":"1972","unstructured":"Hell P., Rosa A.: Graph decompositions, handcuffed prisoners and balanced $$P$$-designs. Discret. Math. 2, 229\u2013252 (1972).","journal-title":"Discret. Math."},{"key":"1493_CR9","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s00373-015-1564-z","volume":"32","author":"S Jeevadoss","year":"2016","unstructured":"Jeevadoss S., Muthusamy A.: Decomposition of product graphs into paths and cycles of length four. Graphs Combin. 32, 199\u2013223 (2016).","journal-title":"Graphs Combin."},{"key":"1493_CR10","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1186\/1471-2288-14-131","volume":"14","author":"U Krahn","year":"2014","unstructured":"Krahn U., Binder H., K\u00f6nig J.: Visualizing inconsistency in network meta-analysis by independent path decomposition. BMC Med. Res. Methodol. 14, 131 (2014).","journal-title":"BMC Med. Res. Methodol."},{"key":"1493_CR11","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1007\/s003730200061","volume":"18","author":"CH Li","year":"2002","unstructured":"Li C.H., Praeger C.E.: Constructing homogeneous factorisations of complete graphs and digraphs. Graphs Combin. 18, 757\u2013761 (2002).","journal-title":"Graphs Combin."},{"key":"1493_CR12","unstructured":"Lim T.K.: Edge-transitive homogeneous factorisations of complete graphs. Thesis, University of Western Australia (2004)."},{"key":"1493_CR13","unstructured":"Lov\u00e1sz L.: On covering of graphs. In: Erd\u00f6s, P., Katona, G. (eds.) Theory of Graphs, pp. 231\u2013236 (1968)."},{"key":"1493_CR14","unstructured":"Pearce G.: Transitive decompositions of graphs. Thesis, University of Western Australia (2007)."},{"issue":"4","key":"1493_CR15","doi-asserted-by":"publisher","first-page":"303","DOI":"10.4169\/000298910x480775","volume":"117","author":"G Pearce","year":"2010","unstructured":"Pearce G.: Transitive decompositions of graphs and their links with geometry and origami. Am. Math. Mon. 117(4), 303\u2013310 (2010).","journal-title":"Am. Math. Mon."},{"issue":"1","key":"1493_CR16","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1006\/jctb.1996.0012","volume":"66","author":"L Pyber","year":"1996","unstructured":"Pyber L.: Covering the edges of a connected graph by paths. J. Combin. Theory Ser. B 66(1), 152\u2013159 (1996).","journal-title":"J. Combin. Theory Ser. B"},{"issue":"1","key":"1493_CR17","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/0097-3165(83)90040-7","volume":"34","author":"M Tarsi","year":"1983","unstructured":"Tarsi M.: Decomposition of a complete multigraph into simple paths: non-balanced handcuffed designs. J. Combin. Theory Ser. A 34(1), 60\u201370 (1983).","journal-title":"J. Combin. Theory Ser. A"},{"key":"1493_CR18","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/0012-365X(93)90408-L","volume":"116","author":"K Ushio","year":"1993","unstructured":"Ushio K.: G-designs and related designs (English summary). Discret. Math. 116, 299\u2013311 (1993).","journal-title":"Discret. Math."}],"container-title":["Designs, Codes and Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-024-01493-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10623-024-01493-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-024-01493-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,22]],"date-time":"2024-11-22T21:24:57Z","timestamp":1732310697000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10623-024-01493-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,3]]},"references-count":18,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["1493"],"URL":"https:\/\/doi.org\/10.1007\/s10623-024-01493-9","relation":{},"ISSN":["0925-1022","1573-7586"],"issn-type":[{"type":"print","value":"0925-1022"},{"type":"electronic","value":"1573-7586"}],"subject":[],"published":{"date-parts":[[2024,10,3]]},"assertion":[{"value":"16 August 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 July 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 September 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 October 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}