The reducibility of optimal 1-planar graphs

Abstract

A graph is reducible if it is the lexicographic product of two smaller non-trivial graphs. It is well-known a 1-planar graph with $n(\ge 3)$ vertices has at most $4n-8$ edges, and a graph $G$ with $n$ vertices is optimal if $G$ has exactly $4n-8$ edges. In this paper, we characterize the reducibility of optimal 1-planar graphs. This work is motivated by a problem posed by Bucko and Czap in 2015, which concerns determining the 1-planarity of the lexicographic product of a graph and two isolated vertices.

arXiv comment17 pages