内周 (グラフ理論)

数学のグラフ理論の分野における内周（ないしゅう、）とは、グラフに含まれる最小の閉路の長さのことを言うR. Diestel, Graph Theory, p.8.  3rd Edition, Springer-Verlag, 2005。もしもグラフが閉路を含まないなら（すなわち、無閉路グラフであるなら）、その内周は無限大と定義される。例えば、（平方）4-閉路グラフの内周は4である。格子グラフの内周も4である。三角形メッシュの内周は3である。内周が4以上のグラフは、である。

 ケージ 
立方体グラフ（すべての頂点の次数が3であるグラフ）で、その内周が（可能な限り最小な） g であるようなものは、g-ケージ（あるいは (3,g)-ケージ）として知られる。ピーターセングラフは唯一つの 5-ケージであり（内周が5であるような最小の立方体グラフである）、ヒーウッドグラフは唯一つの 6-ケージ、マギーグラフは唯一つの 7-ケージ、は唯一つの 8-ケージである. Electronic supplement to the book Distance-Regular Graphs (Brouwer, Cohen, and Neumaier 1989, Springer-Verlag).。与えられた内周に対して、複数のケージが存在することもある。例えば、70個の頂点を持つ非同型な10-ケージは、三つ存在する：と、およびである。

 内周とグラフ彩色 
任意の正の整数 g と χ に対して、内周が少なくとも g であり、彩色数が少なくとも χ であるようなグラフが存在する：例えば、はトライアングルフリーで彩色数が 4 であり、そのグラフを構成するための構成法を繰り返すことで、任意の大きさの彩色数を備えるトライアングルフリーなグラフを構成することが出来る。ポール・エルデシュは、を用いて、初めてその一般的な結果を証明した.。厳密に言うと彼は、各辺が含まれるかどうかが確率 n(1 − g)/g で独立に決定されるような頂点数 n のは、n が無限大へと向かうにつれて 1 に近付くような確率に対して、長さが g 以下であるような閉路を多くとも n/2 個含むが、大きさが n/2k であるような独立集合は含まない、ということを証明した。したがって、それぞれの短閉路（short cycle）から一つ頂点を取り除くことにより、内周が g より大きく、各彩色の同色集合が小さいためにどのような彩色においても少なくとも k 色が必要となるような、より小さいグラフが得られる。

 関連のある概念 
グラフの奇内周（odd girth）および偶内周（even girth）とは、それぞれ最小の奇閉路および偶閉路の長さのことを言う。

非自明な閉路の最小の長さを考えることで、内周は、における1-シストールやより高位のシストールとしての自然な一般化が可能となる。

 参考文献 

Category:グラフ不変量
Category:グラフ理論
Category:数学に関する記事