Non-1-Planarity of Lexicographic Products of Graphs

Abstract

In this paper, we show the non-1-planarity of the lexicographic product of a theta graph and K2. This result completes the proof of the conjecture that a graph G ◦ K2 is 1-planar if and only if G has no edge belonging to two cycles.

Keywords

• 1-planar graph
• lexicographic product
• 05c10