Cancellation and regularity for planar, 3-connected Kronecker products
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910706078580736 |
|---|---|
| author | De March, Ruben Maffucci, Riccardo W. |
| author_facet | De March, Ruben Maffucci, Riccardo W. |
| contents | We investigate several properties of Kronecker (direct, tensor) products of graphs that are planar and $3$-connected (polyhedral, $3$-polytopal). This class of graphs was recently characterised and constructed by the second author [15].
Our main result is that cancellation holds for the Kronecker product of graphs when the product is planar and $3$-connected (it is known that Kronecker cancellation may fail in general). Equivalently, polyhedral graphs are Kronecker products in at most one way. This is a special case of the deep and interesting question, open in general, of Kronecker product cancellation for simple graphs: when does $A\wedge C\simeq B\wedge C$ imply $A\simeq B$?
We complete our investigation on simultaneous products by characterising and constructing the planar graphs that are Cartesian products in two distinct ways, and the planar, $3$-connected graphs that are both Kronecker and Cartesian products.
The other type of results we obtain are in extremal graph theory. We classify the polyhedral Kronecker products that are either face-regular or vertex-regular graphs. The face-regular ones are certain quadrangulations of the sphere, while the vertex-regular ones are certain cubic graphs (duals of maximal planar graphs). We also characterise, and iteratively construct, the face-regular subclass of graphs minimising the number of vertices of degree $3$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_13473 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Cancellation and regularity for planar, 3-connected Kronecker products De March, Ruben Maffucci, Riccardo W. Combinatorics 05C76, 05C35, 05C10, 05C75, 05C85, 52B05, 52B10 We investigate several properties of Kronecker (direct, tensor) products of graphs that are planar and $3$-connected (polyhedral, $3$-polytopal). This class of graphs was recently characterised and constructed by the second author [15]. Our main result is that cancellation holds for the Kronecker product of graphs when the product is planar and $3$-connected (it is known that Kronecker cancellation may fail in general). Equivalently, polyhedral graphs are Kronecker products in at most one way. This is a special case of the deep and interesting question, open in general, of Kronecker product cancellation for simple graphs: when does $A\wedge C\simeq B\wedge C$ imply $A\simeq B$? We complete our investigation on simultaneous products by characterising and constructing the planar graphs that are Cartesian products in two distinct ways, and the planar, $3$-connected graphs that are both Kronecker and Cartesian products. The other type of results we obtain are in extremal graph theory. We classify the polyhedral Kronecker products that are either face-regular or vertex-regular graphs. The face-regular ones are certain quadrangulations of the sphere, while the vertex-regular ones are certain cubic graphs (duals of maximal planar graphs). We also characterise, and iteratively construct, the face-regular subclass of graphs minimising the number of vertices of degree $3$. |
| title | Cancellation and regularity for planar, 3-connected Kronecker products |
| topic | Combinatorics 05C76, 05C35, 05C10, 05C75, 05C85, 52B05, 52B10 |
| url | https://arxiv.org/abs/2411.13473 |