On matrix product factorization of Cayley graphs
Discrete Applied Mathematics · 2027-01 · 396 · 366-382
DOI: 10.1016/j.dam.2026.09.037 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete Applied Mathematics, 2027-01. Verfasst von Allen W. Herman und 1 weiteren Autor:innen. Die Arbeit nennt 12 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: NSERC.
Abstract (Originalsprache)
We study when the adjacency matrix of a Cayley graph factors as the product of two adjacency matrices of Cayley graphs. Let $G$ be a finite group and let $U\subseteq G\setminus \{e\}$ be symmetric. Writing $A(G;U)$ for the adjacency matrix of the Cayley graph of $G$ with respect to $U$, we prove that for symmetric subsets $S,T,U$ of $G\setminus \{e\}$, $A(G;U)=A(G;S)\,A(G;T)$ if and only if $U=ST$ and each $u\in U$ has a unique representation $u=st$, equivalently $\bigl(\sum_{s\in S}s\bigr)\bigl(\sum_{t\in T}t\bigr)=\sum_{u\in U}u$ in the group algebra. When $S,T,U$ are unions of conjugacy classes, this is characterized character-theoretically by $\chi(U)=\chi(S)\chi(T)/\chi(1)$ for all $\chi\in\mathrm{Irr}(G)$. In addition, for abelian groups, we identify $A(G;S)A(G;T)$ with the $0\!-\!1$ convolution $\mathbf{1}_S*\mathbf{1}_T$, so factorability is equivalent to $(S,T)$ being a Sidon pair, i.e., $(S-S)\cap(T-T)=\{0\}$. For cyclic groups, we reformulate factorability via mask polynomials and reduce to prime-power components using the Chinese Remainder Theorem. We also analyze dihedral groups $D_{2n}$, presenting infinite families of factorable generating sets, and give explicit constructions of subsets whose Cayley graphs do and do not admit such factorizations.
Förderung
- NSERC
Zitieren
APA
Herman, A. W., & Miraftab, B. (2027). On matrix product factorization of Cayley graphs. Discrete Applied Mathematics, 396, 366-382. https://doi.org/10.1016/j.dam.2026.09.037
Vancouver
Herman AW, Miraftab B. On matrix product factorization of Cayley graphs. Discrete Applied Mathematics. 2027;396:366-382. doi:10.1016/j.dam.2026.09.037
BibTeX
@article{Herman2027,
author = {Herman, Allen W. and Miraftab, Bobby},
title = {On matrix product factorization of Cayley graphs},
journal = {Discrete Applied Mathematics},
year = {2027},
volume = {396},
pages = {366--382},
doi = {10.1016/j.dam.2026.09.037}
}
EUVIMED