← All problems

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

5 years old · traced to

Let GG be a connected graph. Its density is

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

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

Refreshed
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 TkT_k is cyclically orderable exactly for k≤4k\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; Θ1,2,5\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

Solutions 0

No solutions have been posted yet.