Kajitani, Ueno and Miyano's conjecture on cyclically orderable graphs

About 5 years old · traced to 2021

Let $G$ be a connected graph. Its density is

d(G)=\frac{|E(G)|}{|V(G)|-1}.

The graph $G$ is uniformly dense if $d(H)\leq d(G)$ for every connected subgraph $H$ of $G$ . A graph is cyclically orderable if it has a cyclic ordering of its edges such that every cyclically consecutive $|V(G)|-1$ edges induce a spanning tree. Kajitani, Ueno and Miyano's conjecture. A connected graph $G$ 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

Primary source

Cedric Xia, Joseph Zhang and Allan Zhou, “A Project on Cyclic Ordering of Some Families of Graphs”, arXiv:2211.09654 (2022).

Additional 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.

Posted 1 month ago · edited 3 weeks ago

Progress summary

Refreshed 3 weeks ago

Open

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 $T_k$ is cyclically orderable exactly for $k\leq 4$ .
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; $\Theta_{1,2,5}$ 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

No solutions have been posted yet.