Article in press
Authors:
Title:
The matching extendability of optimal $1$-embedded graphs on the projective plane
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2024-05-20 , Revised: 2025-01-15 , Accepted: 2025-01-15 , Available online: 2025-02-25 , https://doi.org/10.7151/dmgt.2581
Abstract:
In this paper, we discuss matching extendability
of optimal $1$-projective plane graphs (abbreviated as O1PPG),
which are drawn on the projective plane $P^2$ so that every edge crosses
another edge at most once, and have $n$ vertices and exactly $4n- 4$ edges.
We first show that every O1PPG of even order is $1$-extendable.
Next, we characterize $2$-extendable O1PPG's in terms of
a separating cycle consisting of only non-crossing edges.
Moreover, we characterize O1PPG's having connectivity exactly $5$.
Using the characterization, we further identify three independent edges
in those graphs that are not extendable.
Keywords:
$1$-embeddable graph, projective plane, perfect matching
References:
- R.E.L. Aldred, K.-i. 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 - 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 - 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 - K.-i. 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 - K.-i. Kawarabayashi and K. Ozeki, $4$-connected projective-planar graphs are Hamiltonian-connected, J. Combin. Theory Ser. B 112 (2015) 36–69.
https://doi.org/10.1016/j.jctb.2014.11.006 - 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 - 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.
- A. Nakamoto, Triangulations and Quadrangulations of Surfaces (Ph.D Thesis, Keio University, 1996).
- C.St.J.A. Nash-Williams, Unexplored and semi-explored territories in graph theory, in: New Directions in Graph Theory, F. Harary (Ed(s)), (Academic Press, New York 1973) 149–186.
- K. Noguchi and Y. Suzuki, Relationship among triangulations, quadrangulations and optimal $1$-planar graphs, Graphs Combin. 31 (2015) 1965–1972.
https://doi.org/10.1007/s00373-015-1568-8 - 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 - 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 - M.D. Plummer, Recent progress in matching extension, in: Building Bridges, Bolyai Soc. Math. Stud. 19, M.Grőtschel, G.O.H. Katona and G. Sági (Ed(s)), (Springer, Berlin, Heidelberg 2008) 427–454.
https://doi.org/10.1007/978-3-540-85221-6\_14 - G. Ringel, Ein Sechsfarbenproblem auf der Kugel, Abh. Math. Semin. Univ. Hambg. 29 (1965) 107–117.
https://doi.org/10.1007/BF02996313 - 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 - 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
Close