The reducibility of optimal 1-planar graphs
| Autor: | Zhang, Licheng, Huang, Yuanqiu |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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 ~(\ge3)$ 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. Comment: 17 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|