论文标题
火柴形图中的小型顶点的数量
The number of small-degree vertices in matchstick graphs
论文作者
论文摘要
Matchstick图是平面中的无交叉单位距离图。 Harbourth（1981）提出了确定是否存在火柴形图的问题，其中每个顶点的学位恰好$ 5 $。 1982年，Blokhuis提供了不存在的证据。 Kurz和Pinchasi（2011）使用充电方法发现了较短的证明。我们将它们的方法与等级不等式相结合，以表明在$ n $顶点上有$ω（\ sqrt {n}）$ VERTICES，最多$ 4 $，这是渐近紧的。
A matchstick graph is a crossing-free unit-distance graph in the plane. Harborth (1981) proposed the problem of determining whether there exists a matchstick graph in which every vertex has degree exactly $5$. In 1982, Blokhuis gave a proof of non-existence. A shorter proof was found by Kurz and Pinchasi (2011) using a charging method. We combine their method with the isoperimetric inequality to show that there are $Ω(\sqrt{n})$ vertices in a matchstick graph on $n$ vertices that are of degree at most $4$, which is asymptotically tight.
