ホフマン–シングルトングラフとは？わかりやすく解説

ホフマン–シングルトングラフ
命名者	Alan J. Hoffman; Robert R. Singleton
頂点	50
辺	175
半径	2
直径	2
内周	5
自己同型	252,000; (PSU(3,52):2)
彩色数	4
彩色指数	7
特性	強正則グラフ; 対称グラフ; ハミルトングラフ; 整グラフ; ケージ; ムーアグラフ
種数	29
	テンプレートを表示

ホフマン–シングルトングラフ。10個の相異なる五角形の辺を青色で彩色している。

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

構成法

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

五角形と五芒星による構成

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

代数的性質

ホフマン–シングルトングラフの隣接行列の固有多項式は、 $(x-7)(x-2)^{28}(x+3)^{21}$ 。よってホフマン–シングルトングラフは整グラフ（隣接行列の任意の固有値が整数）となる。

部分グラフ

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

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

注釈・出典

^ ^a ^b Weisstein, Eric W. "Hoffman-Singleton Graph". MathWorld (英語).
^ Hafner, P. R. "The Hoffman-Singleton Graph and Its Automorphisms." J. Algebraic Combin. 18, 7-12, 2003.
^ Royle, G. "Re: What is the Edge Chromatic Number of Hoffman-Singleton?" GRAPHNET@istserv.nodak.edu posting. Sept. 28, 2004. [1]
^ Conder, M.D.E.; Stokes, K.: "Minimum genus embeddings of the Hoffman-Singleton graph", preprint, August 2014.
^ Brouwer, Andries E., Hoffman-Singleton graph .
^ Hoffman, Alan J.; Singleton, Robert R. (1960), “Moore graphs with diameter 2 and 3”, IBM Journal of Research and Development 5 (4): 497–504, doi:10.1147/rd.45.0497, MR0140437 .

参考文献

Benson, C. T.; Losey, N. E. (1971), “On a graph of Hoffman and Singleton”, Journal of Combinatorial Theory. Series B 11 (1): 67–79, doi:10.1016/0095-8956(71)90015-3, ISSN 0095-8956, MR0281658
Holton, D.A.; Sheehan, J. (1993), The Petersen graph, Cambridge University Press, pp. 186 and 190, ISBN 0-521-43594-3 .

ホフマン–シングルトングラフとは？わかりやすく解説