On the number of generalized cospectral mates of graphs

この論文「On the number of generalized cospectral mates of graphs（グラフの一般化スペクトル共スペクトルなグラフの個数について）」は、スペクトルグラフ理論における重要な未解決問題の一つである「グラフがその一般化スペクトルによって一意に決定されるか（DGS: Determined by Generalized Spectrum）」という問いを、定性的な「決定されるか否か」から、定量的な「いくつの非同型グラフが同じ一般化スペクトルを共有しうるか」という問題へと拡張し、その個数に対する厳密な上界を導出した研究です。

以下に、論文の技術的な要約を問題設定、手法、主要な貢献、結果、および意義に分けて詳述します。

1. 問題設定 (Problem)

• 背景: グラフ $G$ のスペクトル（隣接行列の固有値の多重集合）のみならず、その補グラフ $\bar{G}$ のスペクトルも含めたペア $(\text{Spec}(G), \text{Spec}(\bar{G}))$ を「一般化スペクトル」と呼びます。一般に、同型なグラフは同じ一般化スペクトルを持ちますが、逆は必ずしも成り立ちません。同じ一般化スペクトルを持つ非同型なグラフの集合を「一般化スペクトル共スペクトルなグラフ（generalized cospectral mates）」と呼びます。
• 既存の課題: これまで、特定のグラフが DGS であるか（共スペクトルなグラフが自分自身のみであるか）を判定する研究は進んでいましたが、DGS ではない場合、具体的に「いくつの共スペクトルなグラフが存在しうるか」という定量的な上限を一般化して導出する研究は限られていました。
• 本研究の目的: 歩行行列（Walk Matrix）の算術的性質を利用し、一般化スペクトル共スペクトルなグラフの個数に対する明示的な上界を導出すること。

2. 手法と理論的枠組み (Methodology)

本研究の核心は、**歩行行列（Walk Matrix）の Smith 標準形（SNF）と、共スペクトルなグラフを結びつける有理直交行列のレベル（Level）**の間の深い関係性にあります。

• 歩行行列と制御性:
  グラフ $G$ の歩行行列 $W(G)$ を $n \times n$ 行列 $[e, Ae, \dots, A^{n-1}e]$ と定義します（$e$ は全 1 列ベクトル）。$W(G)$ が非特異な場合、グラフは「制御可能（controllable）」と呼ばれます。
• 一般化スペクトルと有理直交行列:
  制御可能なグラフ $G$ と一般化スペクトル共スペクトルなグラフ $H$ の間には、有理数成分を持つ直交行列 $Q$ が一意に存在し、$Q^T A(G) Q = A(H)$ および $Qe = e$ を満たします（Theorem 2.1）。
• 行列のレベル（Level）:
  有理行列 $Q$ のレベル $\ell(Q)$ を、$xQ$が整数行列となる最小の正の整数$x$ と定義します。
  • $\ell(Q) = 1$ の場合、$Q$ は置換行列となり、$H$ は $G$ と同型です。
  • $\ell(Q) > 1$ の場合、$H$ は $G$ と非同型な共スペクトルなグラフとなります。
• Smith 標準形（SNF）の制約:
  歩行行列 $W(G)$ の SNF の不変因子 $d_1 | d_2 | \dots | d_n$ を利用します。特に、最後の不変因子 $d_n(W(G))$ の素因数分解が、許容されるレベル $\ell(Q)$ の値を制限します。
• 対象とするグラフ族 $F_n$:
  本研究は、以下の条件を満たす制御可能グラフの族 $F_n$ に焦点を当てています：
  1. $d_{\lceil n/2 \rceil}(W(G)) = 1$
  2. $d_{n-1}(W(G)) = 2$
     この条件は、有限体上のランク制約（$\text{rank}_p(W(G))$）を強め、行列の構造を厳密に制御するために導入されています。

3. 主要な貢献と定理 (Key Contributions & Theorems)

本研究は以下の 2 つの主要な定理を証明しました。

定理 1.1: レベルによる同型性の一意性

族 $F_n$ に属するグラフ $G$ について、$G$ と一般化スペクトル共スペクトルなグラフ $H_1, H_2$ が存在し、それぞれに対応する有理直交行列 $Q_1, Q_2$ のレベルが等しい（$\ell(Q_1) = \ell(Q_2)$）場合、$H_1$ と $H_2$ は同型です（$H_1 \cong H_2$）。

• 意味: 一般化スペクトル共スペクトルなグラフの「非同型な個数」は、許容される「レベルの値の個数」によって上から抑えられることを示しています。

定理 1.2: 共スペクトルなグラフの個数の上界

$G \in F_n$ であり、$W(G)$ の最後の不変因子 $d_n(W(G))$ の素因数分解を $\prod_{j=1}^m p_j^{k_j}$ とします。このとき、$G$ が持つ一般化スペクトル共スペクトルなグラフの個数は最大で以下の値となります：
$$\left( \prod_{j=1}^m k_j \right) - 1$$

• 導出のロジック:
  1. 行列 $Q$ のレベル $\ell(Q)$ は $d_n(W(G))$ の約数でなければなりません。
  2. 族 $F_n$ の条件と SNF の性質（特に $\text{rank}_p$ の制約）を用いると、各素因数 $p_j$ について、$\ell(Q)$ の指数は $0$から$k_j - 1$ の範囲に制限されることが示されます。
  3. したがって、可能なレベルの総数は $\prod k_j$ 通りです。
  4. そのうち $\ell(Q)=1$ は同型なグラフ（自分自身）に対応するため、これを除いた $\prod k_j - 1$ が非同型な共スペクトルなグラフの最大個数となります。

4. 結果と検証 (Results & Evaluation)

• ** tight な例の構築:**
  $n=10$ のグラフ $G$ に対して、$d_{10}(W(G)) = 2 \times 3^2 \times 5^2 \times 43$ となる例を構成しました。
  • 定理 1.2 による上界計算：$(1+1)(2+1)(2+1)(1+1) - 1 = 2 \times 3 \times 3 \times 2 - 1 = 35$ ではなく、指数の和ではなく「指数の個数」の積を計算する必要があります（原文の計算ロジックに従うと、$k_j$ は指数そのものです。$2^1, 3^2, 5^2, 43^1$ なので、$k_1=1, k_2=2, k_3=2, k_4=1$。積は $1 \times 2 \times 2 \times 1 = 4$。したがって上界は $4-1=3$）。
  • 実際には、このグラフ $G$ にはちょうど 3 つの非同型な共スペクトルなグラフ（$H_1, H_2, H_3$）が存在し、それぞれレベルが 3, 15, 5 でした。これは定理 1.1 の「レベルが異なれば非同型」という主張と一致し、定理 1.2 の上界が**tight（達成可能）**であることを実証しました。
• 数値実験:
  各次数 $n$ に対して 10,000 個のランダムグラフ（辺の確率 0.5）を生成し、族 $F_n$ に属するグラフの割合を調査しました。
  • 結果、$n$ が大きくなるにつれて、ランダムグラフの約 39% が族 $F_n$ に属することが確認されました。これは、導出された上界が非常に広範なグラフクラスに適用可能であることを示しています。

5. 意義と将来の展望 (Significance & Conclusion)

• 理論的意義:
  • これまで「DGS であるか否か」の二値的な議論が主流だった分野において、「DGS でない場合、その非一意性の上限はどれくらいか」という定量的な回答を初めて提供しました。
  • 歩行行列の SNF という代数的構造と、グラフの共スペクトル性の関係を明確に結びつけ、有理直交行列のレベルという新しいパラメータを導入しました。
• 実用的意義:
  • 導出された上界は、グラフの同型判定や、特定のスペクトルを持つグラフの探索アルゴリズムにおいて、探索空間を大幅に削減する指針となります。
  • 約 39% のランダムグラフに適用可能であるため、実世界のネットワーク解析などへの応用可能性が高いです。
• 将来の展望:
  • 族 $F_n$ の定義にある不変因子の制約（$d_{\lceil n/2 \rceil}=1, d_{n-1}=2$）を緩和し、より広いグラフクラスへの一般化。
  • 符号付きラプラシアン行列や距離行列など、他の行列を用いた場合の同様の上限の導出。
  • 全 1 ベクトル $e$ 以外の制御入力ベクトルを用いた場合の検討。

総括すると、この論文はスペクトルグラフ理論において、代数的整数論（Smith 標準形）の手法を駆使して、グラフの構造的特徴とスペクトル的な非一意性の関係を定量化した画期的な成果です。