Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2501.02726 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909450393092096 |
|---|---|
| author | Koizumi, Shohei Suzuki, Yusuke |
| author_facet | Koizumi, Shohei Suzuki, Yusuke |
| contents | In this paper, we discuss optimal $1$-toroidal graphs (abbreviated as O1TG), which are drawn on the torus so that every edge crosses another edge at most once, and has $n$ vertices and exactly $4n$ edges. We first consider connectivity of O1TGs, and give the characterization of O1TGs having connectivity exactly $k$ for each $k\in \{4, 5, 6, 8\}$. In our argument, we also show that there exists no O1TG having connectivity exactly $7$. Furthermore, using the result above, we discuss extendability of matchings, and give the characterization of $1$-, $2$- and $3$-extendable O1TGs in turn. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_02726 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Connectivity and matching extendability of optimal $1$-embedded graphs on the torus Koizumi, Shohei Suzuki, Yusuke Combinatorics In this paper, we discuss optimal $1$-toroidal graphs (abbreviated as O1TG), which are drawn on the torus so that every edge crosses another edge at most once, and has $n$ vertices and exactly $4n$ edges. We first consider connectivity of O1TGs, and give the characterization of O1TGs having connectivity exactly $k$ for each $k\in \{4, 5, 6, 8\}$. In our argument, we also show that there exists no O1TG having connectivity exactly $7$. Furthermore, using the result above, we discuss extendability of matchings, and give the characterization of $1$-, $2$- and $3$-extendable O1TGs in turn. |
| title | Connectivity and matching extendability of optimal $1$-embedded graphs on the torus |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2501.02726 |