MathLabs

未解決問題、組合せ論と離散数学、1967年に提起

優美な木予想

未解決

m=∣V∣−1m = |V| - 1 本の辺をもつ任意の有限木 T=(V,E)T = (V, E) は優美なラベリングをもつ。すなわち、単射 f:V→{0,1,…,m}f: V \to \{0, 1, \dots, m\} であって、各辺 uv∈Euv \in E に誘導される重み ∣f(u)−f(v)∣|f(u) - f(v)| がすべて異なり、したがって集合 {1,2,…,m}\{1, 2, \dots, m\} に一致するものが存在する。

研究の最前線 2026年時点

2026年現在、優美な木予想は一般には未解決のままである。頂点数 n≤35n \le 35 のすべての木について計算機で検証されており、道、毛虫グラフ、対称木、オリーブ木、クモ型木、直径 55 以下の木などの構造化された族については証明されている。任意の大きな木に対しては、確率的手法と吸収法によって漸近的な緩和（mm 辺の木が {0,1,…,(1+o(1))m}\{0, 1, \dots, (1 + o(1))m\} の範囲のラベルで優美にラベル付けできることや、K2m+1K_{2m+1} 内に虹色の木として埋め込めること）が証明されているが、ラベル範囲の o(m)o(m) の余剰を完全に無くすことは現在の手法では達成されていない。

既知の最良の結果

  • 頂点数 n≤35n \le 35 のすべての木は優美であることが網羅的な計算機探索によって確認されている（n≤27n \le 27 は1998年のオルドレッド・マッケイ、n≤35n \le 35 は2010年の方文杰による）。
  • 道、毛虫グラフ、葉が高々 44 個の木、直径が高々 55 の木、オリーブ木、および対称木は、いかなるサイズであっても優美であることが証明されている。
  • リンゲルの分解予想は mm 辺をもつ十分大きなすべての木 TT に対して成り立ち（モンゴメリー、ポクロフスキー、スダコフ、2020/2021年）、有界次数の木は {0,1,…,(1+o(1))m}\{0, 1, \dots, (1 + o(1))m\} への漸近的な優美ラベリングをもつ。

使われた手法と限界

手法達成したこと限界
帰納的 α\alpha-評価と木の貼り合わせ二分割されたラベル範囲をシフトして貼り合わせることで、毛虫グラフ、制限された形のロブスター木、オリーブ木、直径 55 以下の木に対する明示的な優美ラベリングを構成した。すべての木が α\alpha-評価をもつわけではなく（例えば次数 33 の頂点をもつある種の木）、不規則な分岐が帰納的な貼り合わせに必要な連続区間構造を壊してしまう。
虹色部分グラフと分配的吸収法（モンゴメリー・ポクロフスキー・スダコフ）巡回距離彩色のもとで十分大きな任意の mm 辺の木を K2m+1K_{2m+1} の虹色部分グラフとして埋め込み、大きな mm に対するリンゲルの予想を完全に解決した。Z2m+1\mathbb{Z}_{2m+1} における巡回距離は 2m+12m+1 を法として折り返すのに対し、優美なラベリングでは折り返しなしで {0,1,…,m}\{0, 1, \dots, m\} 内の厳密な絶対値差を実現する必要がある。

未解決の問い

  • すべてのロブスター木（すべての葉および葉に隣接する頂点を除くと道になる木、1979年にベルモンが優美であると予想）は優美か。
  • 次数が有界な十分大きなすべての mm 辺の木 TT は、{0,1,…,m}\{0, 1, \dots, m\} への厳密な優美ラベリングをもつか。

参考文献

  1. Alexander Rosa (1967). On certain valuations of the vertices of a graph
  2. Joseph A. Gallian (2022). A dynamic survey of graph labeling
  3. Richard Montgomery, Alexey Pokrovskiy, Benny Sudakov (2021). A proof of Ringel's conjecture · DOI:10.1007/s00039-021-00576-2 · arXiv:2001.02665