On the number of edges of restricted matchstick graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915318251651072 |
|---|---|
| author | Gehér, Panna Pach, János Swanepoel, Konrad Tóth, Géza |
| author_facet | Gehér, Panna Pach, János Swanepoel, Konrad Tóth, Géza |
| contents | A graph whose vertices are points in the plane and whose edges are noncrossing straight-line segments of unit length is called a \emph{matchstick graph}. We prove two somewhat counterintuitive results concerning the maximum number of edges of such graphs in two different scenarios.
First, we show that there is a constant $c>0$ such that every triangle-free matchstick graph on $n$ vertices has at most $2n-c\sqrt{n}$ edges. This statement is not true for any $c>\sqrt2.$
We also prove that for every $r>0$, there is a constant $\varepsilon(r)>0$ with the property that every matchstick graph on $n$ vertices contained in a disk of radius $r$ has at most $(2-\varepsilon(r))n$ edges. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_01589 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the number of edges of restricted matchstick graphs Gehér, Panna Pach, János Swanepoel, Konrad Tóth, Géza Combinatorics A graph whose vertices are points in the plane and whose edges are noncrossing straight-line segments of unit length is called a \emph{matchstick graph}. We prove two somewhat counterintuitive results concerning the maximum number of edges of such graphs in two different scenarios. First, we show that there is a constant $c>0$ such that every triangle-free matchstick graph on $n$ vertices has at most $2n-c\sqrt{n}$ edges. This statement is not true for any $c>\sqrt2.$ We also prove that for every $r>0$, there is a constant $\varepsilon(r)>0$ with the property that every matchstick graph on $n$ vertices contained in a disk of radius $r$ has at most $(2-\varepsilon(r))n$ edges. |
| title | On the number of edges of restricted matchstick graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2506.01589 |