2025/01/06 by Koizumi, Shohei, Suzuki, Yusuke
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2501.02726
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∈ \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.