Maximal 1-plane graphs with dominating vertices

• Published in: Applied mathematics and computation 2023-11, Vol.457, p.128206, Article 128206
• Main Authors: Ding, Zongpeng, Huang, Yuanqiu, Zhang, Licheng
• Format: Article
• Language: English
• Subjects: Density; Dominating vertex; Maximal 1-plane graph
• ISSN: 0096-3003; 1873-5649
• DOI: 10.1016/j.amc.2023.128206

•We observed that any maximal 1-plane graph with at most 6 dominating vertices. Then they provided a nice characterization for the structure for any maximal 1-plane graph with k dominating vertices for k = 3; 4; 5; 6.•For the maximal 1-plane graphs with 2 dominating vertices, we obtained tight lower bounds for the number of edges of G.•In addition, we present similar results for maximal 1-plane graphs with 1 dominating vertex. The new (nice) results here settle the open problem of Ouyang et al. in [Applied Mathematics and Computation 362:124537, 2019]. A graph G is called 1-planar if it can be drawn in the plane so that each edge is crossed by at most one other edge. A graph, together with a 1-planar drawing is called 1-plane. A graph is maximal 1- planar (1-plane), if we cannot add any missing edge so that the resulting graph is still 1-planar (1-plane). Let G be a maximal 1-plane graph of order n and k dominating vertices. In this paper, we first provide a complete characterization on G for 3≤k≤6. Then we prove that G has at least 52n−4 edges for k=2, and this bound is tight. Finally, we obtain that G has at least 73n−103 edges for k=1. Our results also settle an open problem posed by Ouyang et al. in [Applied Mathematics and Computation 362:124537, 2019].