On the Restricted Edge-Cuts of Optimal 1-Planar Graphs

Abstract

The restricted edge-connectivity of a graph is the minimum size of an edge-cut whose removal leaves every component with at least two vertices. In 2024, Zhang et al. showed that the restricted edge-connectivity of any optimal $1$-planar graph belongs to $\{8,10,12\}$. In this paper, we exclude $8$ as a possible value, thereby proving that the restricted edge-connectivity is either $10$ or $12$, and both values are attainable. Furthermore, we show that the restricted edge-connectivity of a 6-connected optimal 1-planar graph equals $10$ if and only if the graph contains an edge whose two endvertices both have degree $6$. As a key ingredient, we characterize the structure of vertex-induced subgraphs on $n$ vertices with $4n-9$ edges in optimal 1-planar graphs, and use this characterization to establish a connection between restricted edge-cuts and vertex-cuts in optimal 1-planar graphs.

arXiv comment11 pages, 1 figure