Joins of 1-planar graphs
Joins of 1-planar graphs
复制标题
DOI：
10.1007/s10114-014-4017-3
复制
发表时间：
2014-10
期刊：
影响因子：
--
通讯作者：
J. Czap;Dávid Hudák;T. Madaras
中科院分区：
文献类型：
--
作者：
J. Czap;Dávid Hudák;T. Madaras
一个图称为1-平面的，如果它允许在平面中绘图，使得每条边最多交叉一次。本文研究了1-平面图的联。证明了当图的联的两个元素都至少有三个顶点时，联G +His是1-平面的当且仅当图对[G，H]被[C3 <$C3，C3]，[C4，C4]，[C4，C3]，[K2，1，1，P3]中的一个子图优化.如果一个元素最多有两个顶点，那么我们给出了较大元素的几个充分必要条件。
A graph is called 1-planar if it admits a drawing in the plane such that each edge is crossed at most once. In this paper, we study 1-planar graph joins. We prove that the joinG+His 1-planar if and only if the pair [G, H] is subgraph-majorized by one of pairs [C3∪C3,C3], [C4,C4], [C4,C3], [K2,1,1,P3] in the case when both elements of the graph join have at least three vertices. If one element has at most two vertices, then we give several necessary/sufficient conditions for the bigger element.