Constructions stemming from non-separating planar graphs and their Colin de Verdi\`ere invariant
| Autor: | Pavelescu, Andrei, Pavelescu, Elena |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Zdroj: | Algebr. Geom. Topol. 24 (2024) 555-568 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.2140/agt.2024.24.555 |
| Popis: | A planar graph $G$ is said to be non-separating if there exists an embedding of $G$ in $\mathbb{R}^2$ such that for any cycle $\mathcal{C}\subset G$, all vertices of $G\setminus \mathcal{C}$ are within the same connected component of $\mathbb{R}^2\setminus \mathcal{C}$. Dehkordi and Farr classified the non-separating planar graphs as either outerplanar graphs, subgraphs of wheel graphs, or subgraphs of elongated triangular prisms. We use maximal non-separating planar graphs to construct examples of maximal linkless graphs and maximal knotless graphs. We show that for a maximal non-separating planar graph $G$ with $n\ge 7$ vertices, the complement $cG$ is $(n-7)-$apex. This implies that the Colin de Verdi\`ere invariant of the complement $cG$ satisfies $\mu(cG) \le n-4$. We show this to be an equality. As a consequence, the conjecture of Kotlov, Lov\`asz, and Vempala that for a simple graph $G$, $\mu(G)+\mu(cG)\ge n-2$ is true for 2-apex graphs $G$ for which $G-\{u,v\}$ is planar non-separating. It also follows that complements of non-separating planar graphs of order at least nine are intrinsically linked. We prove that the complements of non-separating planar graphs $G$ of order at least ten are intrinsically knotted. Comment: 14 pages, 12 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|