Remarks on the joins of 1-planar graphs

Zhangdong Ouyang, Jun Ge and Yichao Chen

Applied Mathematics and Computation, 2019, vol. 362, issue C, -

Abstract: A graph is called NIC-planar if it admits a drawing in the plane such that each edge is crossed at most once and two pairs of crossing edges share at most one vertex. NIC-planarity generalizes IC-planarity, which allows a vertex to be incident to at most one crossing edge, and specializes 1-planarity, which only requires at most one crossing each edge. It is known that any 1-planar (NIC-planar) graph of order n has at most 4n−8 (3.6n−7.2) edges and that this bound is tight. In this paper, we show that every 1-planar (NIC-planar) graph of order n with a dominating vertex has at most 4n−9 (3.5n−7.5) edges and this bound is tight for infinitely many values of n. Moreover, we derive tight upper bounds on the density of G, if G+2P1 and G+P2 are 1-planar (NIC-planar), respectively. These results improve some previous results due to Czap et al. and partially answer their open problem in negative. In addition, we also provide a complete characterization of outer 1-planarity of join of two graphs.

Keywords: 1-planar; Crossing number; Drawing; Join product (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300319305168
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:362:y:2019:i:c:16

DOI: 10.1016/j.amc.2019.06.051

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 ().