Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

論文880 の記録のページです。住所（YOI）は https://www.yamagishiyuuki.com/yoi/880 で、論文の本文は下の PDF にあります。ファイルは自分で用意した置き場所（https://yamagishi.sakuraweb.com）に置き、日付の証拠（.ots）を添えています。

本文はサイトの記事でも読めます（2026年10月8日 9:20 に公開します）。

@misc{yamagishi2026yoi880,
  author = {Yamagishi, Yuuki},
  title = {The Second Laplacian Eigenvalue Never Exceeds the Vertex Connectivity and Tells Apart Thin Necks Cut by the Same Number},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/880},
  note = {Preprint, edition 1}
}

日付の証拠（OpenTimestamps）

2026年10月1日に、2 本の PDF の指紋（SHA-256）をまとめて OpenTimestamps に送り、ビットコインのブロック 969440・969456・969461 に記録されました（2026年10月01日 19:28（日本時間））。この .ots があれば、PDF がその時点で存在したことを、このサイトや運営者を信用しなくても、誰でも確かめられます。

書誌

要旨

網の切れにくさは、何点抜けば切れるかで測る、と思いやすい。本稿は、ラプラシアンの固有値でも切れにくさを測り、点で切る数と並べて、点 $6$ 個のすべてのグラフで数える。新しい定理も法則も主張しない。

第一に、ゼロ固有値は成分を数える。点 $6$ 個のすべてのグラフ $32768$ 個で、ゼロ固有値の個数は、辺をたどって数えた成分の数と一致した（第2節）。

第二に、二番目の固有値は、点で切る数を超えない。完全グラフ以外の連結グラフ $26703$ 個すべてで、二番目の固有値 $\le$ 点連結度で、等しいのは $3111$ 個、割合 $\mathbf{0.116504}$ である（第3節）。

第三に、これが本稿の芯である。同じ点の数で切れるグラフでも、二番目の固有値は首の細さを測り分ける。一点で切れるグラフ $15336$ 個で、二番目の固有値は道の $\mathbf{0.267949}$ から星の $1.000000$ まで散らばり、平均は $\mathbf{0.696682}$ である（第3節）。

第四に、点 $6$ 個では、固有値は点連結度の一つ下とのあいだに収まった。点連結度 $2$ で $1$ から $2$、$3$ で $2$ から $3$、$4$ はすべて $4$、完全グラフは $6$ で、点連結度 $1$〜$3$ ではすべて「点連結度 $-1$」と「点連結度」のあいだに入った（第3節）。

第五に、道の値は式と合う。点 $6$ 個の道の二番目の固有値は、$2(1-\cos(\pi/6))$ と差 $10^{-9}$ 未満で一致した（第3節）。

第六に、分離子は、整数で数える点連結度を問うか、連続の値で測る二番目の固有値を問うかである。点連結度は何点で切れるかだけを答え、固有値は切り口のまわりがどれだけ細いかまで答える（第4節）。

キーワード：グラフラプラシアン、代数的連結度、点連結度、固有値、フィードラーの不等式

Abstract

It is easy to assume that a network’s robustness is measured by how many vertices must be removed to cut it.This paper also measures robustness by Laplacian eigenvalues and counts, over all graphs on $6$ vertices, how it compares with the vertex cut size.No new theorem or law is claimed.

First, zero eigenvalues count components: in all $32768$ graphs on $6$ vertices, the number of zero eigenvalues matched the number of components counted by following edges (Section 2).

Second, the second eigenvalue never exceeds the vertex cut size: in all $26703$ connected graphs other than the complete graph, second eigenvalue $\le$ vertex connectivity, with equality in $3111$, a share of $\mathbf{0.116504}$ (Section 3).

Third, and this is the core. Among graphs cut by the same number of vertices, the second eigenvalue tells apart thin necks: among the $15336$ graphs cut by one vertex, it ranges from $\mathbf{0.267949}$ for the path to $1.000000$ for the star, averaging $\mathbf{0.696682}$ (Section 3).

Fourth, on $6$ vertices, the eigenvalue stayed within one below the connectivity: connectivity $2$ gives $1$ to $2$, $3$ gives $2$ to $3$, all of connectivity $4$ give $4$, and the complete graph $6$; for connectivity $1$ to $3$ it always lay between one less than the connectivity and the connectivity (Section 3).

Fifth, the path’s value matches the formula: the second eigenvalue of the path on $6$ vertices matched $2(1-\cos(\pi/6))$ within $10^{-9}$ (Section 3).

Sixth, the separator is whether one asks about vertex connectivity, counted as an integer, or the second eigenvalue, measured as a continuous value: connectivity answers only how many vertices cut the graph; the eigenvalue also answers how thin the region around the cut is (Section 4).

Keywords: graph Laplacian, algebraic connectivity, vertex connectivity, eigenvalue, Fiedler’s inequality

版の記録

ここの PDF（倉庫の v1）は第1版（2026年9月）の原稿から作りました。ファイルは版ごとに分けて置いています（/yoi/880/v1/ の下）。中身を直すときは、このファイルを書き換えず、新しい版を足します（住所 https://www.yamagishiyuuki.com/yoi/880 はいつも最新の版を指します）。

YOI の一覧へ