Geodesic
The matching extendability of 7-connected maximal 1-plane graphs
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 777-790

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: perfect matching, 7-connected maximal $1$-plane graph, matching extendability 
@article{DMGT_2024_44_2_a18,
     author = {Huang, Yuanqiu and Zhang, Licheng and Wang, Yuxi},
     title = {The matching extendability of 7-connected maximal 1-plane graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {777--790},
     publisher = {mathdoc},
     volume = {44},
     number = {2},
     year = {2024},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a18/}
}
TY  - JOUR
AU  - Huang, Yuanqiu
AU  - Zhang, Licheng
AU  - Wang, Yuxi
TI  - The matching extendability of 7-connected maximal 1-plane graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 777
EP  - 790
VL  - 44
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a18/
LA  - en
ID  - DMGT_2024_44_2_a18
ER  - 
%0 Journal Article
%A Huang, Yuanqiu
%A Zhang, Licheng
%A Wang, Yuxi
%T The matching extendability of 7-connected maximal 1-plane graphs
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 777-790
%V 44
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a18/
%G en
%F DMGT_2024_44_2_a18
Huang, Yuanqiu; Zhang, Licheng; Wang, Yuxi. The matching extendability of 7-connected maximal 1-plane graphs. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 777-790. http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a18/