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 solved high confidence

For finite simple graphs, a nontrivial joined-union decomposition exists exactly when the graph has a proper nonsingleton module; this is polynomial-time decidable, while P4 shows that not every graph decomposes.

Cited literature (2)

proof On prime Cayley graphs (2024)

See linked article · Existing literature or final source version

For finite simple graphs, a nontrivial joined-union decomposition exists exactly when the graph has a proper nonsingleton module; this is polynomial-time decidable, while P4 shows that not every graph decomposes.

Read the literature-status audit
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. These status corrections report results attributed to existing papers or to the final source version. Graph-Theory-LLM-Proofs located and checked the implication; it is not credited as the author of the result. Audit caveat: This uses the standard graph-substitution meaning of joined union; infinite graphs and more restrictive decomposition notions are not addressed.

Auto-reviewed 2026-09-01 with gpt-5.6-sol.

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