Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2504.05721 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908474510671872 |
|---|---|
| author | Zhang, Junyang |
| author_facet | Zhang, Junyang |
| contents | A graph $Γ$ is said to be stable if $\mathrm{Aut}(Γ\times K_2)\cong\mathrm{Aut}(Γ)\times \mathbb{Z}_{2}$ and unstable otherwise. If an unstable graph is connected, non-bipartite and any two of its distinct vertices have different neighbourhoods, then it is called nontrivially unstable. We establish conditions guaranteeing the instability of various graph products, including direct products, direct product bundles, Cartesian products, strong products, semi-strong products, and lexicographic products. Inspired by a condition for the instability of direct product bundles, we propose a new sufficient condition for circulant graphs to be unstable and refine existing instability conditions from the literature. Based on these results, we categorize unstable circulant graphs into two distinct types and further propose a classification framework. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_05721 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Graph product and the stability of circulant graphs Zhang, Junyang Combinatorics A graph $Γ$ is said to be stable if $\mathrm{Aut}(Γ\times K_2)\cong\mathrm{Aut}(Γ)\times \mathbb{Z}_{2}$ and unstable otherwise. If an unstable graph is connected, non-bipartite and any two of its distinct vertices have different neighbourhoods, then it is called nontrivially unstable. We establish conditions guaranteeing the instability of various graph products, including direct products, direct product bundles, Cartesian products, strong products, semi-strong products, and lexicographic products. Inspired by a condition for the instability of direct product bundles, we propose a new sufficient condition for circulant graphs to be unstable and refine existing instability conditions from the literature. Based on these results, we categorize unstable circulant graphs into two distinct types and further propose a classification framework. |
| title | Graph product and the stability of circulant graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2504.05721 |