The minimum orientable genus of the repeated Cartesian product of graphs

Marietta Galea () and John Baptist Gauci ()
Additional contact information
Marietta Galea: University of Malta
John Baptist Gauci: University of Malta

Journal of Combinatorial Optimization, 2025, vol. 49, issue 2, No 14, 13 pages

Abstract: Abstract 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 g such that a given graph G has an embedding on the orientable surface of genus g. 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 s-cube $$Q_i^{(s)}$$ Q i ( s ) is obtained by taking the repeated Cartesian product of i complete bipartite graphs $$K_{s,s}$$ K s , s . We determine the genus of the Cartesian product of the 2r-cube with the repeated Cartesian product of cycles and of the Cartesian product of the 2r-cube with the repeated Cartesian product of paths.

Keywords: Genus; Cartesian product; Complete bipartite graph; Cycle; Path; 05C10; 05C50 (search for similar items in EconPapers)
Date: 2025
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-025-01266-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:49:y:2025:i:2:d:10.1007_s10878-025-01266-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-025-01266-7

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().