Joined Union Decomposition of Cayley Graphs

Question 1.1 · arXiv:2401.06062

arXiv Question high confidence— first stated 2024-01-11

Authors: Maria Chudnovsky, Michal Cizek, Logan Crew, Ján Mináč, Tung T. Nguyen, Sophie Spirkl, Nguyên Duy Tân

Status partial high confidence

Question 1.1 asks whether a given graph can be decomposed as the joined union of smaller graphs, which is equivalent to detecting non-trivial homogeneous sets (modules). The source paper itself provides a complete algebraic characterization for Cayley graphs: Cay(G,S) has a non-trivial homogeneous set if and only if there exists a non-trivial subgroup H such that every right coset Hc (for c in S minus H) is entirely contained in S (Theorem 3.4). The paper has since appeared in the Journal of Combinatorics (2025). A 2024 follow-up (arXiv:2403.05635) extends this line of research to p-unitary Cayley graphs over finite rings, providing necessary and sufficient conditions for primality (non-decomposability) in that more general setting.

Cited literature (1)

partial On certain properties of the p-unitary Cayley graph over a finite ring (2024)

not confirmed (authors not retrieved from abstract page) · arXiv preprint · arXiv:2403.05635

Extends the prime Cayley graph characterization from arXiv:2401.06062 to p-unitary Cayley graphs over finite rings, providing necessary and sufficient conditions for such graphs to be prime (i.e., not decomposable as a joined union of smaller graphs).

Reviewer notes. Question 1.1 is a broad motivating question that the source paper answers for Cayley graphs via algebraic conditions on the group and generating set; for general graphs, decomposition as a joined union is the classical modular decomposition problem (well-studied). The paper has been published in the Journal of Combinatorics (Volume 0, 2025). The follow-up arXiv:2403.05635 explicitly builds on 'prior classification of prime unitary Cayley graphs' (its reference [7]) and extends to p-unitary Cayley graphs, strongly suggesting it continues the program of arXiv:2401.06062. Author names of arXiv:2403.05635 were not retrieved.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Question. Given a graph $\Gamma$, can we decompose it as the joined union of smaller graphs?

Context

This question is motivated by the study of multilayer networks and phase oscillators, where decomposing a network as a joined union of smaller graphs allows solutions to be broadcast from a reduced representation system to the full network. The paper addresses this question specifically for Cayley graphs using tools from group theory and ring theory.

Notes. The paper answers this question in the special case of Cayley graphs; the general question for arbitrary graphs is classical and studied via modular decomposition theory.

Source paper

On prime Cayley graphs
Maria Chudnovsky, Michal Cizek, Logan Crew, Ján Mináč, Tung T. Nguyen, Sophie Spirkl, Nguyên Duy Tân · 2024-01-11
https://arxiv.org/abs/2401.06062