Determining the minimum size of maximal 1-plane graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929718028140544 |
|---|---|
| author | Huang, Yuanqiu Ouyang, Zhangdong Zhang, Licheng Dong, Fengming |
| author_facet | Huang, Yuanqiu Ouyang, Zhangdong Zhang, Licheng Dong, Fengming |
| contents | A 1-plane graph is a graph together with a drawing in the plane in such a way that each edge is crossed at most once. A 1-plane graph is maximal if no edge can be added without violating either 1-planarity or simplicity. Let $m(n)$ denote the minimum size of a maximal $1$-plane graph of order $n$. Brandenburg et al. established that
$m(n)\ge 2.1n-\frac{10}{3}$ for all $n\ge 4$, which was improved by Barát and Tóth to $m(n)\ge \frac{20}{9}n-\frac{10}{3}$. In this paper, we confirm that $m(n)=\left\lceil\frac{7}{3}n\right\rceil-3$ for all $n\ge 5$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_11696 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Determining the minimum size of maximal 1-plane graphs Huang, Yuanqiu Ouyang, Zhangdong Zhang, Licheng Dong, Fengming Combinatorics 05C10 A 1-plane graph is a graph together with a drawing in the plane in such a way that each edge is crossed at most once. A 1-plane graph is maximal if no edge can be added without violating either 1-planarity or simplicity. Let $m(n)$ denote the minimum size of a maximal $1$-plane graph of order $n$. Brandenburg et al. established that $m(n)\ge 2.1n-\frac{10}{3}$ for all $n\ge 4$, which was improved by Barát and Tóth to $m(n)\ge \frac{20}{9}n-\frac{10}{3}$. In this paper, we confirm that $m(n)=\left\lceil\frac{7}{3}n\right\rceil-3$ for all $n\ge 5$. |
| title | Determining the minimum size of maximal 1-plane graphs |
| topic | Combinatorics 05C10 |
| url | https://arxiv.org/abs/2502.11696 |