Remarks on the joins of 1-planar graphs
Remarks on the joins of 1-planar graphs
复制标题
关于 1-平面图连接的备注
DOI：
10.1016/j.amc.2019.06.051
复制
发表时间：
2019-12
影响因子：
4
通讯作者：
Chen Yichao
中科院分区：
文献类型：
--
作者：
Ouyang Zhangdong;Ge Jun;Chen Yichao
如果一个图允许在平面上画图，使得每一条边至多相交一次，且两对相交边至多共用一个顶点，则称该图为NIC-平面图。NIC-平面性概括了IC-平面性，其允许顶点至多与一个交叉边相关联，并且专门化1-平面性，其仅需要每个边至多一个交叉。已知任何n阶的1-平面（NIC-平面）图最多有4个n-8（3.6 n-7.2）条边，并且这个界是紧的。在本文中，我们证明了每个具有控制点的n阶1-平面（NIC-平面）图最多有4个n-9（3.5 n-7.5）条边，并且这个界对n的无穷多个值是紧的。此外，当G+ 2 P1和G+ P2分别为1-平面（NIC-平面）时，我们得到了G的密度的紧上界.这些结果改进了Czap等人的一些结果，并部分地回答了他们的公开问题。此外，我们还给出了两个图的联的外1-平面性的一个完整刻画。
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 4 n− 8 (3.6 n− 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 4 n− 9 (3.5 n− 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+ 2 P 1 and G+ P 2 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.
登录
查看更多内容
DOI：
10.1007/s10114-014-4017-3
发表时间：
2014-10
期刊：
Acta Mathematica Sinica, English Series
影响因子：
--
作者：
J. Czap;Dávid Hudák;T. Madaras
通讯作者：
J. Czap;Dávid Hudák;T. Madaras
DOI：
10.26493/1855-3974.10.2d0
发表时间：
2008-06
期刊：
Ars Math. Contemp.
影响因子：
--
作者：
M. Albertson
通讯作者：
M. Albertson
影响因子：
1
作者：
Von H. Schumacher
通讯作者：
Von H. Schumacher
影响因子：
0.9
作者：
V. P. Korzhik;B. Mohar
通讯作者：
V. P. Korzhik;B. Mohar
DOI：
10.1016/j.ipl.2013.01.013
发表时间：
2013-04
期刊：
Inf. Process. Lett.
影响因子：
--
作者：
W. Didimo
通讯作者：
W. Didimo