2025/04/30 by Ouyang, Zhangdong, Huang, Yuanqiu, Zhang, Licheng +1 · 1 citation
#05C10 #05C62 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2504.21558
A 1-planar graph is a graph which has a drawing on the plane such that each edge is crossed at most once. If a 1-planar graph is drawn in that way, the drawing is called a \it 1-plane graph. A graph is maximal 1-plane (or 1-planar) if no additional edge can be added without violating 1-planarity or simplicity. It is known that any maximal 1-plane graph is k-connected for some k with 2≤ k≤ 7. Recently, Huang et al. proved that any maximal 1-plane graph with n (≥ 5) vertices has at least \lceil(7)/(3)n\rceil-3 edges, which is tight for all integers n≥ 5. In this paper, we study k-connected maximal 1-plane graphs for each k with 3≤ k≤ 7, and establish a lower bound for their crossing numbers and a lower bound for their edge numbers, respectively.