Article in volume
Authors:
Title:
The matching extendability of 7-connected maximal 1-plane graphs
PDFSource:
Discussiones Mathematicae Graph Theory 44(2) (2024) 777-790
Received: 2022-04-26 , Revised: 2022-08-25 , Accepted: 2022-08-26 , Available online: 2022-09-15 , https://doi.org/10.7151/dmgt.2470
Abstract:
A graph is 1-planar if it can be drawn in the plane such that each edge is
crossed at most once. A graph, together with a 1-planar drawing is called
1-plane. A graph is said to be $k (\ge 1)$-extendable if every matching of
size $k$ can be extended to a perfect matching. It is known that the
vertex connectivity of a 1-plane graph is at most 7. In this paper, we
characterize the $k$-extendability of $7$-connected maximal $1$-plane graphs.
We show that every $7$-connected maximal $1$-plane graph with even order is
$k$-extendable for $1\le k\le 3$. And any $7$-connected maximal $1$-plane graph
is not $k$-extendable for $4\le k\le 11$. As for $k\ge 12$, any $7$-connected
maximal $1$-plane graph with $n$ vertices is not $k$-extendable unless $n=2k$.
Keywords:
perfect matching, 7-connected maximal $1$-plane graph, matching extendability
References:
- R.E.L. Aldred and M.D. Plummer, Edge proximity and matching extension in planar triangulations, Australas. J. Combin. 29 (2004) 215–224.
- C. Bachmaier, F.J. Brandenburg, K. Hanauer, D. Neuwirth and J. Reislhuber, NIC-planar graphs, Discrete Appl. Math. 232 (2017) 23–40.
https://doi.org/10.1016/j.dam.2017.08.015 - J. Barát and G. Tóth, Improvements on the density of maximal $1$-planar graphs, J. Graph Theory 88 (2018) 101–109.
https://doi.org/10.1002/jgt.22187 - I. Baybars, On $k$-path hamiltonian maximal planar graphs, Discrete Math. 40 (1982) 119–121.
https://doi.org/10.1016/0012-365X(82)90193-5 - T. Biedl, Are highly connected $1$-planar graphs Hamiltonian$?$ (2019).
arXiv: 1911.02153 - T. Biedl, A note on $1$-planar graphs with minimum degree $7$, Discrete Appl. Math. 289 (2021) 230–232.
https://doi.org/10.1016/j.dam.2020.10.004 - T. Biedl and J. Wittnebel, Matchings in $1$-planar graphs with large minimum degree, J. Graph Theory 99 (2022) 217–230.
https://doi.org/10.1002/jgt.22736 - R. Bodendiek, H. Schumacher and K. Wagner, Über $1$-optimale {Graphen}, Math. Nachr. 117(1) (1984) 323–339.
https://doi.org/10.1002/mana.3211170125 - W. Didimo, Density of straight-line $1$-planar graph drawings, Inform. Process. Lett. 113(7) (2013) 236–240.
https://doi.org/10.1016/j.ipl.2013.01.013 - P. Eades, S.-H. Hong, N. Katoh, G. Liotta, P. Schweitzer and Y. Suzuki, A linear time algorithm for testing maximal $1$-planarity of graphs with a rotation system, Theoret. Comput. Sci. 513 (2013) 65–76.
https://doi.org/10.1016/j.tcs.2013.09.029 - I. Fabrici, J. Harant, T. Madaras, S. Mohr, R. Soták and C.T. Zamfirescu, Long cycles and spanning subgraphs of locally maximal $1$-planar graphs, J. Graph Theory 95 (2020) 125–137.
https://doi.org/10.1002/jgt.22542 - 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 - J.P. Gollin, K. Hendrey, A. Methuku, C. Tompkins and X. Zhang, Counting cliques in $1$-planar graphs (2021).
arXiv: 2109.02906 - A. Grigoriev and H.L. Bodlaender, Algorithms for graphs embeddable with few crossings per edge, Algorithmica 49 (2007) 1–11.
https://doi.org/10.1007/s00453-007-0010-x - J. Hopcroft and R. Tarjan, Efficient planarity testing, J. ACM 21 (1974) 549–568.
https://doi.org/10.1145/321850.321852 - D. Hudák, T. Madaras and Y. Suzuki, On properties of maximal $1$-planar graphs, Discuss. Math. Graph Theory 32 (2012) 737–747.
https://doi.org/10.7151/dmgt.1639 - F. István, On straight-line representation of planar graphs, Acta Univ. Szeged. Sect. Sci. Math. 11 (1948) 229–233.
- 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 - V.P. Korzhik and B. Mohar, Minimal obstructions for $1$-immersions and hardness of $1$-planarity testing, J. Graph Theory 72 (2013) 30–71.
https://doi.org/10.1002/jgt.21630 - Z. Ouyang, Y. Huang and F. Dong, The maximal $1$-planarity and crossing numbers of graphs, Graphs Combin. 37 (2021) 1333–1344.
https://doi.org/10.1007/s00373-021-02320-x - J. Pach and G. Tóth, Graphs drawn with few crossings per edge, Combinatorica 17 (1997) 427–439.
https://doi.org/10.1007/BF01215922 - 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, On $n$-extendable graphs, Discrete Math. 31 (1980) 201–210.
https://doi.org/10.1016/0012-365X(80)90037-0 - 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 - G. Ringel, Ein Sechsfarbenproblem auf der Kugel, Abh. Math. Semin. Univ. Hambg. 29 (1965) 107–117.
https://doi.org/10.1007/BF02996313 - Y. Suzuki, 1-Planar Graphs, in: Beyond Planar Graphs, S.-H. Hong and T. Tokuyama (Ed(s)), (Springer 2020) 47–68.
https://doi.org/10.1007/978-981-15-6533-5_4 - R. Thomas and X.X. Yu, $4$-connected projective-planar graphs are Hamiltonian, J. Combin. Theory Ser. B 62 (1994) 114–132.
https://doi.org/10.1006/jctb.1994.1058 - W. Yang, Y. Wang, W. Wang and K.-W. Lih, IC-planar graphs are $6$-choosable, SIAM J. Discrete Math. 35 (2021) 1729–1745.
https://doi.org/10.1137/20M133261X - X. Zhang, H.-J. Wang and L. Xu, Equitable coloring of three classes of $1$-planar graphs, Acta Math. Appl. Sin. Engl. Ser. 34 (2018) 362–372.
https://doi.org/10.1007/s10255-018-0752-z
Close