コンテンツにスキップ

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

出典: フリー百科事典『ウィキペディア(Wikipedia)』
ホフマン–シングルトングラフ
命名者 Alan J. Hoffman
Robert R. Singleton
頂点 50
175
半径 2
直径 2[1]
内周 5[1]
自己同型 252,000
(PSU(3,52):2)[2]
彩色数 4
彩色指数 7[3]
特性 強正則グラフ
対称グラフ
ハミルトングラフ
整グラフ
ケージ
ムーアグラフ
種数 29[4]
テンプレートを表示
ホフマン–シングルトングラフ。10個の相異なる五角形の辺を青色で彩色している。

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

構成法

[編集]

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

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

[編集]

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

代数的性質

[編集]

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

部分グラフ

[編集]

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

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

注釈・出典

[編集]
  1. ^ a b Weisstein, Eric W. "Hoffman-Singleton Graph". mathworld.wolfram.com (英語).
  2. ^ Hafner, P. R. "The Hoffman-Singleton Graph and Its Automorphisms." J. Algebraic Combin. 18, 7-12, 2003.
  3. ^ Royle, G. "Re: What is the Edge Chromatic Number of Hoffman-Singleton?" GRAPHNET@istserv.nodak.edu posting. Sept. 28, 2004. [1]
  4. ^ Conder, M.D.E.; Stokes, K.: "Minimum genus embeddings of the Hoffman-Singleton graph", preprint, August 2014.
  5. ^ Brouwer, Andries E., Hoffman-Singleton graph, http://www.win.tue.nl/~aeb/drg/graphs/Hoffman-Singleton.html .
  6. ^ 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, http://www.research.ibm.com/journal/rd/045/ibmrd0405H.pdf .

参考文献

[編集]

関連項目

[編集]