Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2405.05368 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915116759384064 |
|---|---|
| author | Galea, Marietta Gauci, John Baptist |
| author_facet | Galea, Marietta Gauci, John Baptist |
| contents | 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 modelling interconnection networks. The $s$-cube $Q_i^{(s)}$ is obtained by taking the repeated Cartesian product of $i$ complete bipartite graphs $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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_05368 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The minimum orientable genus of the repeated Cartesian product of graphs Galea, Marietta Gauci, John Baptist Combinatorics 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 modelling interconnection networks. The $s$-cube $Q_i^{(s)}$ is obtained by taking the repeated Cartesian product of $i$ complete bipartite graphs $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. |
| title | The minimum orientable genus of the repeated Cartesian product of graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2405.05368 |