Regular matchstick graphs

DOI10.4169/AMER.MATH.MONTHLY.118.03.264MaRDI QIDQ3085257zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Sascha Kurz, Rom Pinchasi

Publication date 31 March 2011

Published in The American Mathematical Monthly (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.4372

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: A graph G=(V,E) is called a unit-distance graph in the plane if there is an injective embedding of V in the plane such that every pair of adjacent vertices are at unit distance apart. If additionally the corresponding edges are non-crossing and all vertices have the same degree r we talk of a regular matchstick graph. Due to Euler's polyhedron formula we have $rle5$. The smallest known 4-regular matchstick graph is the so called Harborth graph consisting of 52 vertices. In this article we prove that no finite 5-regular matchstick graph exists and provide a lower bound for the number of vertices of 4-regular matchstick graphs.

Recommendations

• scientific article; zbMATH DE number 6881053
• New minimal (4; n)-regular matchstick graphs
• Regular matchstick graphs
• A 3-regular matchstick graph of girth 5 consisting of 54 vertices
• The number of small-degree vertices in matchstick graphs

Cited in

(8)

• The number of small-degree vertices in matchstick graphs
• Bounding the number of edges of matchstick graphs
• A 3-regular matchstick graph of girth 5 consisting of 54 vertices
• On topological graphs with at most four crossings per edge
• A tight bound for the number of edges of matchstick graphs
• General penny graphs are at most \(\frac{43}{18}\)-dense
• scientific article; zbMATH DE number 6881053 (Why is no real title available?)
• Regular matchstick graphs

This page was built for publication: Regular matchstick graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3085257)