{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,14]],"date-time":"2025-03-14T04:28:24Z","timestamp":1741926504051,"version":"3.38.0"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T00:00:00Z","timestamp":1740009600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T00:00:00Z","timestamp":1740009600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100015774","name":"University of Malta","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100015774","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2025,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Determining the minimum genus of a graph is a fundamental optimisation problem in the study of network design and implementation as it gives a measure of non-planarity of graphs. In this paper, we are concerned with determining the smallest value of <jats:italic>g<\/jats:italic> such that a given graph <jats:italic>G<\/jats:italic> has an embedding on the orientable surface of genus <jats:italic>g<\/jats:italic>. In particular, we consider the Cartesian product of graphs since this is a well studied graph operation which is often used for modeling interconnection networks. The <jats:italic>s<\/jats:italic>-cube <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$Q_i^{(s)}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msubsup>\n                    <mml:mi>Q<\/mml:mi>\n                    <mml:mi>i<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>s<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:msubsup>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> is obtained by taking the repeated Cartesian product of <jats:italic>i<\/jats:italic> complete bipartite graphs <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$K_{s,s}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>K<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mi>s<\/mml:mi>\n                      <mml:mo>,<\/mml:mo>\n                      <mml:mi>s<\/mml:mi>\n                    <\/mml:mrow>\n                  <\/mml:msub>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>. We determine the genus of the Cartesian product of the 2<jats:italic>r<\/jats:italic>-cube with the repeated Cartesian product of cycles and of the Cartesian product of the 2<jats:italic>r<\/jats:italic>-cube with the repeated Cartesian product of paths.<\/jats:p>","DOI":"10.1007\/s10878-025-01266-7","type":"journal-article","created":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T19:09:48Z","timestamp":1740078588000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The minimum orientable genus of the repeated Cartesian product of graphs"],"prefix":"10.1007","volume":"49","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-7925-331X","authenticated-orcid":false,"given":"Marietta","family":"Galea","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6584-8473","authenticated-orcid":false,"given":"John Baptist","family":"Gauci","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,2,20]]},"reference":[{"key":"1266_CR1","doi-asserted-by":"publisher","first-page":"494","DOI":"10.4153\/CJM-1965-048-6","volume":"17","author":"LW Beineke","year":"1965","unstructured":"Beineke LW, Harary F (1965) The Genus of the $$n$$-Cube. Canad. J. Math. 17:494\u2013496","journal-title":"Canad. J. Math."},{"key":"1266_CR2","volume-title":"Chromatic Graph Theory","author":"G Chartrand","year":"2008","unstructured":"Chartrand G, Zhang P (2008) Chromatic Graph Theory. Taylor & Francis"},{"key":"1266_CR3","doi-asserted-by":"crossref","unstructured":"Erickson J, Fox K, Nayyeri A (2012) Global minimum cuts in surface embedded graphs, SIAM: Proc. SODA \u201912, 1309\u20131318","DOI":"10.1137\/1.9781611973099.103"},{"key":"1266_CR4","unstructured":"Euler L (1976) Solutio problematis ad geometriam situs pertinentis, Commentarii Academiae Scientiarum Imperialis Petropolitanae, 8: 128-140 (1736), reprinted and translated in N. L. Biggs, E. K. Lloyd & R. J. Wilson, Graph Theory 1736-1936, Oxford University Press"},{"key":"1266_CR5","unstructured":"Garey MR, Johnson DS (1979) Computers and Intractability. A Guide to the theory of NP-completeness, Bell Telephone Laboratories"},{"key":"1266_CR6","volume-title":"Topological Graph Theory","author":"JL Gross","year":"1987","unstructured":"Gross JL, Tucker TW (1987) Topological Graph Theory. Wiley, New York"},{"key":"1266_CR7","doi-asserted-by":"publisher","DOI":"10.1201\/b16132","volume-title":"Handbook of Graph Theory","author":"JL Gross","year":"2013","unstructured":"Gross JL, Yellen J, Zhang P (2013) Handbook of Graph Theory, 2nd edn. Chapman & Hall\/CRC","edition":"2"},{"issue":"4","key":"1266_CR8","doi-asserted-by":"publisher","first-page":"352","DOI":"10.1080\/00029890.2020.1867472","volume":"128","author":"RH Hammack","year":"2021","unstructured":"Hammack RH, Kainen PC (2021) A New View of Hypercube Genus. Amer. Math. Monthly 128(4):352\u2013359","journal-title":"Amer. Math. Monthly"},{"key":"1266_CR9","first-page":"332","volume":"24","author":"PJ Heawood","year":"1890","unstructured":"Heawood PJ (1890) Map colour theorem. Q. J. Math. 24:332\u2013338","journal-title":"Q. J. Math."},{"key":"1266_CR10","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/s00373-022-02488-w","volume":"38","author":"C Millichap","year":"2022","unstructured":"Millichap C, Salinas F (2022) Embedding Grid Graphs on Surfaces. Graphs Combin. 38:87","journal-title":"Graphs Combin."},{"key":"1266_CR11","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1002\/jgt.3190040105","volume":"4","author":"T Pisanski","year":"1980","unstructured":"Pisanski T (1980) Genus of Cartesian products of regular bipartite graphs. J. Graph Theory 4:31\u201342","journal-title":"J. Graph Theory"},{"key":"1266_CR12","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1002\/jgt.3190060403","volume":"6","author":"T Pisanski","year":"1982","unstructured":"Pisanski T (1982) Nonorientable genus of Cartesian products of regular graphs. J. Graph Theory 6:191\u2013402","journal-title":"J. Graph Theory"},{"key":"1266_CR13","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/BF02993245","volume":"28","author":"GV Ringel","year":"1965","unstructured":"Ringel GV (1965) Das geschlecht des vollst\u00e4ndigen paaren graphen. Abhandlungen aus dem Mathematischen Seminar der Universit\u00e4t Hamburg 28:139\u2013150","journal-title":"Abhandlungen aus dem Mathematischen Seminar der Universit\u00e4t Hamburg"},{"key":"1266_CR14","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1007\/BF02960735","volume":"20","author":"GV Ringel","year":"1955","unstructured":"Ringel GV (1955) \u00dcber drei Kombinatorische Probleme am $$n$$-dimensionalen W\u00fcrfel und W\u00fcrfelgitter. Abhandlungen aus dem Mathematischen Seminar der Universit\u00e4t Hamburg 20:10\u201319","journal-title":"Abhandlungen aus dem Mathematischen Seminar der Universit\u00e4t Hamburg"},{"key":"1266_CR15","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1007\/BF01162967","volume":"72","author":"G Sabidussi","year":"1959","unstructured":"Sabidussi G (1959) Graph multiplication. Math. Z. 72:446\u2013457","journal-title":"Math. Z."},{"key":"1266_CR16","doi-asserted-by":"publisher","first-page":"515","DOI":"10.4153\/CJM-1957-060-7","volume":"9","author":"G Sabidussi","year":"1957","unstructured":"Sabidussi G (1957) Graphs with given Group and given Graph-Theoretical Properties. Canad. J. Math. 9:515\u2013525","journal-title":"Canad. J. Math."},{"key":"1266_CR17","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2022.103667","volume":"110","author":"T Sun","year":"2023","unstructured":"Sun T (2023) Settling the genus of the $$n$$-prism. European J. Combin. 110:103667","journal-title":"European J. Combin."},{"key":"1266_CR18","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1016\/0196-6774(89)90006-0","volume":"10","author":"C Thomassen","year":"1989","unstructured":"Thomassen C (1989) The graph genus problem is NP-complete. J. Algorithms 10:568\u2013576","journal-title":"J. Algorithms"},{"key":"1266_CR19","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1090\/S0002-9947-1970-0281653-3","volume":"151","author":"AT White","year":"1970","unstructured":"White AT (1970) The genus of repeated Cartesian products of bipartite graphs. Trans. Amer. Math. Soc. 151:393\u2013404","journal-title":"Trans. Amer. Math. Soc."},{"issue":"12","key":"1266_CR20","first-page":"8","volume":"14","author":"C-L Wu","year":"1981","unstructured":"Wu C-L (1981) Interconnection networks. Computer 14(12):8\u20139","journal-title":"Computer"},{"key":"1266_CR21","first-page":"303","volume":"12","author":"JWT Youngs","year":"1963","unstructured":"Youngs JWT (1963) Minimal imbeddings and the genus of a graph. J. Murh. Mech. 12:303\u2013315","journal-title":"J. Murh. Mech."}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01266-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-025-01266-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01266-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,13]],"date-time":"2025-03-13T21:07:13Z","timestamp":1741900033000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-025-01266-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,20]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["1266"],"URL":"https:\/\/doi.org\/10.1007\/s10878-025-01266-7","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2025,2,20]]},"assertion":[{"value":"23 January 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 February 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have not disclosed any competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"31"}}