ホフマン–シングルトングラフ
ナビゲーションに移動
検索に移動
ホフマン–シングルトングラフとは、50個の頂点と175個の辺からなる7-正則グラフである。これは(50,7,0,1)-強正則グラフであり一意である。[1]このグラフはアラン・ホフマンとロバート・シングルトンによって、ムーアグラフの分類の過程で構成された。またホフマン–シングルトングラフは知られているムーアグラフの中でもっとも頂点数が多いグラフである。[2] 次数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個のピーターセングラフを含む。