2025/02/17 by Huang, Yuanqiu, Ouyang, Zhangdong, Zhang, Licheng +1 · 1 citation
#05C10 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2502.11696
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)≥ 2.1n-(10)/(3) for all n≥ 4, which was improved by Barát and Tóth to m(n)≥ (20)/(9)n-(10)/(3). In this paper, we confirm that m(n)=\lceil(7)/(3)n\rceil-3 for all n≥ 5.