新しい有向グラフ再構築予想

スタニスワフ・ウラムの再構成予想は、グラフ理論における最もよく知られた未解決問題の一つである。フランク・ハラリ^[1]の用語を用いると、次のように述べることができる。GとHが少なくとも3つの頂点を持つ2つのグラフであり、ƒがV(G)からV(H)への一対一変換であり、 G \ { v }とH \ { ƒ ( v ) }がV ( G )のすべての頂点vに対して同型である場合、GとHは同型である。

1964年、ハラリ^[2]は再構成予想を5つ以上の頂点を持つ有向グラフに拡張し、いわゆる有向グラフ再構成予想とした。1964年から1976年の間に、有向グラフ再構成予想を支持する結果が多数発表された。しかし、PKストックマイヤーが任意の大きさの有向グラフ（トーナメントを含む）の反例ペアの無限族をいくつか発見したことで、この予想は誤りであることが証明された。^{[3] [4] [5]}有向グラフ再構成予想の誤りは、再構成予想自体に疑問を投げかけた。ストックマイヤーは、「（再構成）予想を証明するために費やされている多大な労力は、反例を構築するためのより真剣な試みとバランスを取るべきかもしれない」とさえ述べた。^[3]

1979年、ラマチャンドランは、有向グラフ再構築予想を、新有向グラフ再構築予想と呼ばれるやや弱い形で復活させた。有向グラフにおいて、頂点vから（または頂点vへ）入射する弧の数はvの出次数（入次数）と呼ばれ、 od ( v )（またはid ( v )）と表記される。新有向グラフ予想は、次のように述べることができる。^{[6] [7]}

DとE が任意の2つの有向グラフであり、ƒがV ( D )からV ( E )への全単射であり、 D \{ v } とE \{ƒ( v )} が同型であり、V ( D ) のすべてのvに対して ( od ( v )), id ( v )) = ( od (ƒ( v )), id (ƒ( v )))である場合、DとEは同型です。

新しい有向グラフ再構築予想は、無向グラフの場合の再構築予想に帰着します。これは、2 つのグラフの頂点を削除した部分グラフがすべて同型である場合、対応する頂点は同じ次数を持つ必要があるためです。したがって、新しい有向グラフ再構築予想は再構築予想よりも強力ですが、反証された有向グラフ再構築予想よりも弱いです。いくつかの有向グラフ ファミリが新しい有向グラフ再構築予想を満たすことが示されており、これらには有向グラフ再構築予想に対する既知の反例ペアのすべての有向グラフが含まれます。

• 2連結な基底グラフを持つすべての有向グラフがN再構成可能であれば、すべての有向グラフはN再構成可能である。^[8]
• すべての有向グラフがN再構成可能であるのは、次の2つの有向グラフのクラスのいずれかがN再構成可能である場合のみである。ここで、diam(D)とradius(D)は、Dの基礎となるグラフの直径と半径として定義される。^[9]
  1. ^{diam(D) ≤ 2 または diam(D) = diam(D c} ) = 3の有向グラフ
  2. 2連結な基底グラフと半径(D) ≤ 2を持つ有向グラフD

2024年現在、新しい有向グラフ再構築予想に対する反例は知られていない。この予想は現在、次数関連再構築予想としても知られている。