Dyadic Saturation in Cubic Vertex-Transitive Graphs: A Complete PSV Census Theorem up to 1280 and a Mechanism Taxonomy

We study the Erdos-Gyárfás conjecture through a dyadic lens on the class of connected cubic vertex-transitive graphs. For a graph G we dene the dyadic ground length ℓ∗(G) = min{2k ≥4 : C2k (G) ̸= ∅} and the associated valuation v2(G) = log2(ℓ∗(G))−1, setting v2(G) = ∞ when no power-of-two cycle exists. Using the complete Poto£nikSpigaVerret (PSV) census of all cubic vertex-transitive graphs of order at most 1280 (111,360 graphs), we obtain a computational theorem: every census graph contains a cycle of length 4, 8, 16, or 32 (equivalently, v2(G) ≤4 throughout the census window), and no instance with dyadic silence beyond 32 occurs. The elite set v2 = 4 consists of exactly 100 graphs and decomposes cleanly into three disjoint structural routes: Triangle-Crystal (TF = 1) with 53 graphs, Bipartite-Voltage (bipartite) with 30 graphs, and a genuinely non-bipartite, non-crystalline Route 3 with 17 graphs. An odd-girth analysis of the Route-3 elite reveals three species of frustrated symmetry ranging from pentagonal (g = 5) through quasi-bipartite (g= 6, odd girth up to 21) to high-girth extremes (g≥9). We present the route taxonomy, certify all counts and artifacts deterministically (no sampling), and formulate a corrected proof program beyond the census window: since cubic vertex-transitive graphs can have arbitrarily large girth, no constant dyadic lter length can hold order-free; the natural upgrade target is EGC-type dyadic existence together with quantitative control of dyadic depth growth via matching-lattice and quotient/cover methods.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-02-13
DOI
https://doi.org/10.5281/zenodo.18631619
Primary Topic
Theoretical and Computational Physics
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Dyadic Saturation in Cubic Vertex-Transitive Graphs: A Complete PSV Census Theorem up to 1280 and a Mechanism Taxonomy

Jonas Gebendorfer
Zenodo (CERN European Organization for Nuclear Research)
Theoretical and Computational Physics
article

Dyadic Saturation in Cubic Vertex-Transitive Graphs: A Complete PSV Census Theorem up to 1280 and a Mechanism Taxonomy

Jonas Gebendorfer
article en

Abstract

We study the Erdos-Gyárfás conjecture through a dyadic lens on the class of connected cubic vertex-transitive graphs. For a graph G we dene the dyadic ground length ℓ∗(G) = min{2k ≥4 : C2k (G) ̸= ∅} and the associated valuation v2(G) = log2(ℓ∗(G))−1, setting v2(G) = ∞ when no power-of-two cycle exists. Using the complete Poto£nikSpigaVerret (PSV) census of all cubic vertex-transitive graphs of order at most 1280 (111,360 graphs), we obtain a computational theorem: every census graph contains a cycle of length 4, 8, 16, or 32 (equivalently, v2(G) ≤4 throughout the census window), and no instance with dyadic silence beyond 32 occurs. The elite set v2 = 4 consists of exactly 100 graphs and decomposes cleanly into three disjoint structural routes: Triangle-Crystal (TF = 1) with 53 graphs, Bipartite-Voltage (bipartite) with 30 graphs, and a genuinely non-bipartite, non-crystalline Route 3 with 17 graphs. An odd-girth analysis of the Route-3 elite reveals three species of frustrated symmetry ranging from pentagonal (g = 5) through quasi-bipartite (g= 6, odd girth up to 21) to high-girth extremes (g≥9). We present the route taxonomy, certify all counts and artifacts deterministically (no sampling), and formulate a corrected proof program beyond the census window: since cubic vertex-transitive graphs can have arbitrarily large girth, no constant dyadic lter length can hold order-free; the natural upgrade target is EGC-type dyadic existence together with quantitative control of dyadic depth growth via matching-lattice and quotient/cover methods.

Zenodo (CERN European Organization for Nuclear Research)
Openalex Percentile: Top 55%
Theoretical and Computational Physics
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.