ホフマン–シングルトングラフ

ホフマン–シングルトングラフとは、50個の頂点と175個の辺からなる7-正則グラフである。これは(50,7,0,1)-強正則グラフであり一意である。このグラフはアラン・ホフマンとロバート・シングルトンによって、ムーアグラフの分類の過程で構成された。またホフマン–シングルトングラフは知られているムーアグラフの中でもっとも頂点数が多いグラフである。 次数7のムーアグラフであることから、内周は５であり、(7,5)-ケージとなる。

構成法 
さまざまな構成法が知られている。

五角形と五芒星による構成 
５つの五角形Phと５つの五芒星Qiをとる。五角形Phにおいて頂点jからj-1とj+1に辺をひく。また五芒星Qiにおいて頂点jからj-2とj+2に辺をひく。最後に五角形Phの頂点jから五芒星Qjの頂点hi+jに辺をひく。（すべて法５で考える。）

代数的性質 
ホフマン–シングルトングラフの隣接行列の固有多項式は、。よってホフマン–シングルトングラフは整グラフ（隣接行列の任意の固有値が整数）となる。

部分グラフ 
(50,7,0,1)の強正則グラフであることのみから、ホフマン–シングルトングラフが1260個の5-サイクルを持つことを示すことができる。

加えて、ホフマン-シングルトンは525個のピーターセングラフを含む。

注釈・出典

参考文献 
 
 .

関連項目 
 Table of the largest known graphs of a given diameter and maximal degree（英語）

グラフ理論のグラフ
数学に関する記事