摘要
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 join G ＋ H is 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.
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 join G ＋ H is 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.
基金
Supported by the Agency of Slovak Ministry of Education for the Structural Funds of the EU under project ITMS:26220120007
by Science and Technology Assistance Agency under the contract No.APVV-0023-10
by Slovak VEGA grant No.1/0652/12
