The matching extendability of 7-connected maximal 1-plane graphs
Yuanqiu Huang, Licheng Zhang, Yuxi Wang · Discussiones Mathematicae Graph Theory · 2022
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(≥ 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 ≤ k ≤ 3.And any 7-connected maximal 1-plane graph is not k-extendable for 4 ≤ k ≤ 11.As for k ≥ 12, any 7-connected maximal 1-plane graph with n vertices is not k-extendable unless n = 2k.