论文标题
在1平面图中的匹配大小和高度最低度
On the size of matchings in 1-planar graph with high minimum degree
论文作者
论文摘要
图形的匹配是一组没有通用端顶点的边缘。如果将图称为1平面，则该图在平面中录入图纸，以使每个边缘最多一次交叉。最近，Biedl和Wittnebel证明，每1个具有最低度3和$ n \ geq 7 $ Vertices的1平面图具有至少$ \ frac {n+12} {7} $的大小的匹配，对于某些图而言，这很紧。他们还为1平面图中的匹配尺寸提供了紧密的下限，最低度为4或5。在本文中，我们证明，任何具有最低6度和$ n \ geq 36 $顶点的1个平面图的大小至少具有$ \ frac {3n+4} {7} {7} $，并且该下限是紧密的。我们的结果证实了Biedl和Wittnebel提出的猜想。
A matching of a graph is a set of edges without common end vertex. A graph is called 1-planar if it admits a drawing in the plane such that each edge is crossed at most once. Recently, Biedl and Wittnebel proved that every 1-planar graph with minimum degree 3 and $n\geq 7$ vertices has a matching of size at least $\frac{n+12}{7}$, which is tight for some graphs. They also provided tight lower bounds for the sizes of matchings in 1-planar graphs with minimum degree 4 or 5. In this paper, we show that any 1-planar graph with minimum degree 6 and $n \geq 36$ vertices has a matching of size at least $\frac{3n+4}{7}$, and this lower bound is tight. Our result confirms a conjecture posed by Biedl and Wittnebel.
