arXiv preprint ·
Distinguishing invariants of Cayley Graphs, Hamming graphs, and wreath product actions
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Let $Γ$ be a nontrivial group that acts on a graph $G=(V,E)$. The total distinguishing number $D''_Γ(V\cup E)$ (distinguishing index $D'_Γ(E)$) of the action is the least number of labels required for a total labeling (edge labeling) of $G$ so that the only elements of $Γ$ that preserve the labeling belong to the pointwise stabilizer of $V\cup E$ (pointwise stabilizer of $E$). We obtain upper bounds of these invariants for Cayley graphs and under various group actions, including free actions, wreath product actions, and coordinatewise actions on Cartesian powers of graphs. Our first main result shows that, if $Γ$ acts faithfully on $G$, with $|V|\geq 2, |E|\geq 1$ and the natural action of the wreath product $W=Γ\wr S_k$ on $V^k$ induces an action of $W$ on the Cartesian power $G^{k}=(V^{k},E_k)$, then $ D''_{W}(V^k\cup E_k)\le D''_Γ(V\cup E)+k-1 $ for any $k\geq 2$. We also establish the sharpness of several of our bounds through examples involving cyclic, symmetric, and alternating groups. Moreover, we determine these distinguishing invariants for the symmetric group action on Hamming graphs.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Combinatorics
Bounds on Negligible Thresholds in Group Cohomology
A positive answer to Barsotti and Carman's question on unit groups of Burnside rings of fusion systems
Zariski dense hyperbolic 3-manifold groups in $\mathrm{SL}(4,\mathbb{Z})$
Dense Exact Factorizations of Countable Topological Groups
Slim Polygons, Hyperbolicity, and a new Quasi-Isometric Invariant
Get the few papers worth your time in Combinatorics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.