Joins of 1-planar graphs

DOI10.1007/S10114-014-4017-3zbMATH Open1304.05024arXiv1403.6705OpenAlexW3102642860MaRDI QIDQ477875FDOQ477875

Authors: Július Czap, Tomáš Madaras, Dávid Hudák 

Publication date: 10 December 2014

Published in: Acta Mathematica Sinica, English Series (Search for Journal in Brave)

Abstract: A graph is called 1-planar if there exists its 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 (that is, both $G$ and $H$ are subgraphs of graphs of the major pair) by one of pairs $[C_{3}cup{C}_3,C_3],[C_4,C_4],[C_4,C_3],[K_{2,1,1},P_3]$ in the case when both factors of the graph join have at least three vertices. If one factor has at most two vertices, then we give several necessary/sufficient conditions for the bigger factor.

Full work available at URL: https://arxiv.org/abs/1403.6705

Recommendations

• Drawing graph joins in the plane with restrictions on crossings
• Remarks on the joins of 1-planar graphs
• Planarity of joined graphs
• 1-planarity of complete multipartite graphs
• The structure of 1-planar graphs

zbMATH Keywords

1-planar graphjoin product

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Graph theory
• Graphs drawn with few crossings per edge
• Ein Sechsfarbenproblem auf der Kugel
• Title not available (Why is that?)
• The structure of 1-planar graphs
• Fáry's theorem for 1-planar graphs
• Title not available (Why is that?)
• 1-planarity of complete multipartite graphs
• The crossing number of K5,n
• The crossing numbers of join of the special graph on six vertices with path and cycle
• Characterization of join graphs with crossing number zero
• The crossing numbers of join products of paths with graphs of order four
• The Join of Graphs and Crossing Numbers
• On Topological Invariants of the Product of Graphs

Cited In (7)

• Planarity of joined graphs
• On the sizes of bipartite 1-planar graphs
• 1-embeddability of complete multipartite graphs on the projective plane
• Non-1-planarity of lexicographic products of graphs
• Remarks on the joins of 1-planar graphs
• An annotated bibliography on 1-planarity
• Drawing graph joins in the plane with restrictions on crossings

This page was built for publication: Joins of 1-planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q477875)