Classification and Construction of Planar, 3-Connected Kronecker Products
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913221280006144 |
|---|---|
| author | Maffucci, Riccardo W. |
| author_facet | Maffucci, Riccardo W. |
| contents | We give a complete classification of the Kronecker (i.e. direct) product graphs that are planar and $3$-connected (i.e. $3$-polytopal). They are all of the form \[H\wedge K_2,\] where $H$ is a $2$-connected graph, possibly non-planar, and satisfying specific properties that we will describe.
Our proof is constructive, in the sense that we prescribe how to obtain all such graphs $H$, by adding a few edges in a specific way to a given planar, bipartite graph, that is either $3$-connected, or semi-hyper-$2$-connected.
Moreover, for $H$ planar, we also give a more precise characterisation of this graph, regarding the number of its odd regions, and how they intersect.
If $H\wedge K_2$ is a $3$-polytope, then we have $δ(H\wedge K_2)=3$, so that the connectivity of $H\wedge K_2$ is $3$, and the connectivity of $H$ is either $2$ or $3$.
We also briefly discuss which Cartesian and strong products are $3$-polytopal. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_01407 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Classification and Construction of Planar, 3-Connected Kronecker Products Maffucci, Riccardo W. Combinatorics 05C75, 05C76, 05C62, 05C10, 05C40, 52B05, 52B10, 05C85, 05C83 We give a complete classification of the Kronecker (i.e. direct) product graphs that are planar and $3$-connected (i.e. $3$-polytopal). They are all of the form \[H\wedge K_2,\] where $H$ is a $2$-connected graph, possibly non-planar, and satisfying specific properties that we will describe. Our proof is constructive, in the sense that we prescribe how to obtain all such graphs $H$, by adding a few edges in a specific way to a given planar, bipartite graph, that is either $3$-connected, or semi-hyper-$2$-connected. Moreover, for $H$ planar, we also give a more precise characterisation of this graph, regarding the number of its odd regions, and how they intersect. If $H\wedge K_2$ is a $3$-polytope, then we have $δ(H\wedge K_2)=3$, so that the connectivity of $H\wedge K_2$ is $3$, and the connectivity of $H$ is either $2$ or $3$. We also briefly discuss which Cartesian and strong products are $3$-polytopal. |
| title | Classification and Construction of Planar, 3-Connected Kronecker Products |
| topic | Combinatorics 05C75, 05C76, 05C62, 05C10, 05C40, 52B05, 52B10, 05C85, 05C83 |
| url | https://arxiv.org/abs/2402.01407 |