Kajitani, Ueno and Miyano's conjecture on cyclically orderable graphs
Let be a connected graph. Its density is
The graph is uniformly dense if for every connected subgraph of . A graph is cyclically orderable if it has a cyclic ordering of its edges such that every cyclically consecutive edges induce a spanning tree. Kajitani, Ueno and Miyano's conjecture. A connected graph is cyclically orderable if and only if it is uniformly dense. This gives a density-theoretic characterization of cyclic base orderings; the source states that the necessity was proved by Kajitani, Ueno and Miyano, while the converse is the conjectural direction.
References
2 papers in this index state this conjecture (2021–2022). The statement above is taken from the most recent of them; the others are arXiv:2110.00892.
Source: Cedric Xia, Joseph Zhang and Allan Zhou, “A Project on Cyclic Ordering of Some Families of Graphs”, arXiv:2211.09654 (2022).
Progress summary
No public source found a proof or counterexample; only special graph families are known.
The conjecture asserts that a connected graph is cyclically orderable exactly when it is uniformly dense. Kajitani, Ueno, and Miyano proved the necessity; the converse remains unsettled in the latest source.
Known results
- The triangular grid graph is cyclically orderable exactly for .
- Vertex-amalgamations of cyclically orderable graphs remain cyclically orderable under the stated equal-size or equal-density hypotheses.
- Generalized theta graphs satisfy necessary density inequalities; is not cyclically orderable.
- Generalized theta graphs with equal path lengths are cyclically orderable.
Current status (as of September 2026): the necessity direction and several graph-family cases are settled, but the converse—that every uniformly dense connected graph is cyclically orderable—remains open.
Sources
Solutions 0
No solutions have been posted yet.