Maximal 1-plane graphs with dominating vertices

Zongpeng Ding, Yuanqiu Huang and Licheng Zhang

Applied Mathematics and Computation, 2023, vol. 457, issue C

Abstract: 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].

Keywords: Drawing; Density; Maximal 1-plane graph; Dominating vertex (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300323003752
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:457:y:2023:i:c:s0096300323003752

DOI: 10.1016/j.amc.2023.128206

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().