2025-11-20T23:10:16.079459

Ihara zeta functions for some simple graph families

Chico, Mattman, Richards

The reciprocal of the Ihara zeta function of a graph is a polynomial invariant introduced by Ihara in 1966. Scott and Storm gave a method to determine the coefficients of the polynomial. Here we simplify their calculation and determine the zeta function for all graphs of rank two. We verify that it is a complete invariant for such graphs: If $G_1$ and $G_2$ are of rank two, then $G_1$ and $G_2$ are isomorphic if and only if they have the same Ihara zeta function. We observe that the reciprocal of the zeta function is an even polynomial if the graph is bipartite. We also determine the zeta function for several graph families: complete graphs, complete bipartite graphs, MÃ¶bius ladders, cocktail party graphs, and all graphs of order five or less. We use the special value $u=1$ to count the spanning trees for these families.

academic

いくつかの単純グラフ族に対するイハラゼータ関数

基本情報

論文ID: 2501.00639
タイトル: Ihara zeta functions for some simple graph families
著者: Maize Chico, Thomas W. Mattman, Alex Richards
分類: math.CO（組合論）
発表日時: 2024年12月31日
論文リンク: https://arxiv.org/abs/2501.00639

要旨

グラフのイハラゼータ関数の逆数は、1966年にイハラによって導入された多項式不変量である。ScottとStormは多項式の係数を決定する方法を与えた。ここでは、彼らの計算を簡略化し、秩2のすべてのグラフに対するゼータ関数を決定する。そのようなグラフに対して、それが完全不変量であることを検証する： $G_1$ と $G_2$ が秩2である場合、 $G_1$ と $G_2$ が同型であることと、同じイハラゼータ関数を持つことは同値である。ゼータ関数の逆数は、グラフが二部グラフである場合、偶多項式であることを観察する。また、複数のグラフ族に対するゼータ関数を決定する：完全グラフ、完全二部グラフ、メビウスラダー、カクテルパーティグラフ、および5次以下のすべてのグラフ。特殊値 $u=1$ を使用して、これらの族の全域木を数える。

研究背景と動機

問題記述

本研究は、グラフのイハラゼータ関数に焦点を当てている。これは1966年にイハラによって導入された多項式不変量である。主に以下の問題を解決する：

計算方法の簡略化：ScottとStormは多項式係数を決定する方法を提供したが、計算が複雑であり、簡略化が必要である
秩2グラフの完全分類：すべての秩2グラフのゼータ関数を決定し、完全不変量としての性質を検証する
特殊グラフ族のゼータ関数：複数の重要なグラフ族のイハラゼータ関数を計算する

重要性

理論的意義：イハラゼータ関数はグラフ論と数論を結びつけ、グラフの重要な代数的不変量である
応用価値：グラフの分類、全域木の計数など、実際的な問題に適用可能である
計算複雑性：既存の方法は計算が複雑であり、簡略化された方法は実用的価値を持つ

既存方法の限界

ScottとStormの方法は理論的には完全であるが、以下の点で限界がある：

計算過程が煩雑で複雑である
特定のグラフ族に対して直接的な公式が不足している
グラフの構造的特性を十分に活用して計算を簡略化していない

核心的貢献

Scott-Storm方法の簡略化：イハラゼータ多項式の係数を計算するための簡略化された公式を提案した（定理1.5）
秩2グラフの完全分類：すべての秩2グラフのゼータ関数を決定した。これには3つの主要な族が含まれる：二重環グラフ、重複環グラフ、および手錠グラフ
完全不変量性質の証明：秩2のグラフに対して、イハラゼータ関数が完全不変量であることを証明した（定理1.7）
二部グラフの性質の確立：二部グラフのゼータ多項式が偶多項式であることを証明した（定理1.6）
重要なグラフ族のゼータ関数の計算：完全グラフ、完全二部グラフ、メビウスラダー、カクテルパーティグラフなどを含む
全域木計数への応用： $u=1$ での特殊値を利用して、各グラフ族の全域木の数を計算した

方法の詳細

核心的定義

グラフのイハラゼータ関数は以下のように定義される： $\zeta_G(u)^{-1} = (1-u^2)^{r-1}\det(I-Au+Qu^2)$

ここで：

$A$ は隣接行列
$Q = D-I$ 、 $D$ は次数行列
$r = |E|-|V|+1$ はグラフの秩

主要な技術的革新

1. 係数計算の簡略化方法（定理1.5）

グラフ $G$ に対して、ゼータ関数の逆数 $\zeta_G(u)^{-1}$ は多項式 $\sum c_k u^k$ であり、以下が成り立つ： $c_k = \sum_{L \in L_k(L^oG)} (-1)^{r(L)}$

ここで $L_k(L^oG)$ は有向線グラフ $L^oG$ における正確に $k$ 個の頂点を持つ線形部分グラフの集合であり、 $r(L)$ は $L$ 内のサイクル数である。

2. 二部グラフの偶多項式性質（定理1.6）

$G$ が二部グラフである場合、 $\zeta_G(u)^{-1}$ は偶多項式であることを証明した。すなわち、奇数次の項の係数がゼロである。

主要な洞察：二部グラフ内の有向サイクルは必ず偶数の長さを持つ必要があり、これにより線形部分グラフは偶数個の頂点上にのみ存在することができる。

3. 秩2グラフの分類

二重環グラフ $G_{m,n}$ ：2つのサイクルが1つの頂点を共有する $\zeta_{G_{m,n}}(u)^{-1} = -3u^{2(m+n)} + 2u^{m+2n} + 2u^{2m+n} + u^{2n} + u^{2m} - 2u^n - 2u^m + 1$

重複環グラフ $G_{m,n,p}$ ：2つのサイクルが $p$ 本の連続した辺を共有する $\zeta_{G_{m,n,p}}(u)^{-1} = -4u^{2m+2n-2p} + u^{2m+2n-4p} + 2u^{m+2n-2p} + 2u^{2m+n-2p} + u^{2n} + u^{2m} + 2u^{m+n} - 2u^{m+n-2p} - 2u^n - 2u^m + 1$

手錠グラフ $H_{m,n,l}$ ：2つのサイクルが長さ $l$ のパスで接続される $\zeta_{H_{m,n,l}}(u)^{-1} = -4u^{2m+2n+2l} + u^{2m+2n} + 4u^{2m+n+2l} + 4u^{m+2n+2l} - 2u^{2m+n} - 2u^{m+2n} - 4u^{m+n+2l} + 4u^{m+n} + u^{2n} + u^{2m} - 2u^n - 2u^m + 1$