DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2024): 0.8

5-year Journal Impact Factor (2024): 0.7

CiteScore (2024): 2.1

SNIP (2024): 1.162

Discussiones Mathematicae Graph Theory

Article in press

Authors:

S. Koizumi

Syohei Koizumi

Niigata University

email: f24a039c@mail.cc.niigata-u.ac.jp

0009-0006-6950-5957

Y. Suzuki

Yusuke Suzuki

Tsuruoka National College of Technology, Tsuruoka, Yamagat

email: y-suzuki@math.sc.niigata-u.ac.jp

Title:

Connectivity and matching extendability of optimal 1-embedded graphs on the torus

PDF

Source:

Discussiones Mathematicae Graph Theory

Received: 2025-04-10 , Revised: 2025-09-19 , Accepted: 2025-09-19 , Available online: 2025-10-29 , https://doi.org/10.7151/dmgt.2609

Abstract:

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.

Keywords:

1-embeddable graph, torus, connectivity, perfect matching

References:

  1. R.E.L. Aldred, K. Kawarabayashi and M.D. Plummer, On the matching extendability of graphs in surfaces, J. Combin. Theory Ser. B 98 (2008) 105–115.
    https://doi.org/10.1016/j.jctb.2007.06.001
  2. R.E.L. Aldred and M.D. Plummer, Proximity thresholds for matching extension in planar and projective planar triangulations, J. Graph Theory 67 (2011) 38–46.
    https://doi.org/10.1002/jgt.20511
  3. A. Altshuler, Hamilton circuits in some maps on the torus, Discrete Math. 1 (1972) 299–314.
    https://doi.org/10.1016/0012-365X(72)90037-4
  4. J. Fujisawa, K. Segawa and Y. Suzuki, The matching extendability of optimal $1$-planar graphs, Graphs Combin. 34 (2018) 1089–1099.
    https://doi.org/10.1007/s00373-018-1932-6
  5. K. Kawarabayashi, S. Negami, M.D. Plummer and Y. Suzuki, The $2$-extendability of $5$-connected graphs on surfaces with large representativity, J. Combin. Theory Ser. B 101 (2011) 206–213.
    https://doi.org/10.1016/j.jctb.2011.02.001
  6. S.G. Kobourov, G. Liotta and F. Montecchiani, An annotated bibliography on $1$-planarity, Comput. Sci. Rev. 25 (2017) 49–67.
    https://doi.org/10.1016/j.cosrev.2017.06.002
  7. S. Koizumi and Y. Suzuki, The matching extendability of optimal $1$-embedded graphs on the projective plane, Discuss. Math. Graph Theory 45 (2025) 1233–1248.
    https://doi.org/10.7151/dmgt.2581
  8. T. Nagasawa, K. Noguchi and Y. Suzuki, Optimal $1$-embedded graphs on the projective plane which triangulate other surfaces, J. Nonlinear Convex Anal. 19 (2018) 1759–1770.
  9. A. Nakamoto, Triangulations and Quadrangulations of Surfaces, Ph.D Thesis (Keio University, 1996).
  10. A. Nakamoto and S. Negami, Full-symmetric embeddings of graphs on closed surfaces, Mem. Osaka Kyoiku Univ. Ser. III 49 (2000) 1–15.
  11. S. Negami, Uniqueness and faithfulness of embedding of toroidal graphs, Discrete Math. 44 (1983) 161–180.
    https://doi.org/10.1016/0012-365X(83)90057-2
  12. S. Negami, Uniqueness and Faithfulness of Embedding of Graphs into Surfaces, Ph.D Thesis (Tokyo Institute of Technology, 1985).
  13. M.D. Plummer, A theorem on matchings in the plane, Ann. Discrete Math. 41 (1988) 347–354.
    https://doi.org/10.1016/S0167-5060(08)70473-4
  14. M.D. Plummer, Extending matchings in planar graphs IV, Discrete Math. 109 (1992) 207–219.
    https://doi.org/10.1016/0012-365X(92)90292-N
  15. M.D. Plummer, Recent progress in matching extension, in: Building Bridges, Bolyai Soc. Math. Stud. 19, (Berlin, Springer-Verlag 2008) 427–454.
    https://doi.org/10.1007/978-3-540-85221-6\_14
  16. G. Ringel, Ein Sechsfarbenproblem auf der Kugel, Abh. Math. Semin. Univ. Hambg. 29 (1965) 107–117.
    https://doi.org/10.1007/BF02996313
  17. Y. Suzuki, $K_7$-minors in optimal $1$-planar graphs, Discrete Math. 340 (2017) 1227–1234.
    https://doi.org/10.1016/j.disc.2017.01.022
  18. Y. Suzuki, Generating polyhedral quadrangulations of the projective plane, Ars Math. Contemp. 19 (2019) 153–183.
    https://doi.org/10.26493/1855-3974.1195.c71
  19. Y. Suzuki, $1$-planar graphs, in: Beyond Planar Graphs, S.H. Hong and T. Tokuyama (Ed(s)), (Springer, Singapore 2020) 47–68.
    https://doi.org/10.1007/978-981-15-6533-5_4
  20. K. Sone and Y. Suzuki, Optimal $1$-planar multigraphs, Discrete Math. 346 (2023) 113553.
    https://doi.org/10.1016/j.disc.2023.113553
Close