Remarks on the joins of 1-planar graphs

摘要

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.