Planar-Toroidal Decomposition of $K_{12}$
Abstract
In 1978, Anderson and White asked whether there is a decomposition of $K_{12}$ into two graphs, one planar and one toroidal. Using theoretical arguments and a computer search of all maximal planar graphs of order 12, we show that no such decomposition exists. We further show that if $G$ is planar of order 12 and $H\subseteq\overline{G}$ is toroidal, then $H$ has at least two fewer edges than $\overline{G}$. A computer search found all 123 unique pairs $\left(G,H\right)$ that make this an equality. 9 pages
Fields of Study & Subjects
graph theory and CDMA systems
Mathematics and Applications
Coding theory and cryptography
Publication details
- Journal / source
- Discrete Mathematics & Theoretical Computer Science
- Volume
- vol. 28:2
- Issue
- Graph Theory
- Publication date
- 15 January 2026
- Language
- EN