積分グラフ

グラフ理論の数学分野では、整数グラフとは、隣接行列のスペクトルがすべて整数で構成されるグラフのことである。言い換えれば、隣接行列の特性多項式のすべての根が整数である場合、そのグラフは整数グラフである。 ^{[ 1 ]}

この概念は1974年にフランク・ハラリーとアレン・シュウェンクによって提唱された。^{[ 2 ]}

• 完全グラフK _{n は}、すべてのnに対して整数である。^{[ 2 ]}
• 整数となるサイクルグラフは${\displaystyle C_{3}}$、${\displaystyle C_{4}}$、 そして${\displaystyle C_{6}}$[ ^{2 ]​}
• グラフが整数であれば、その補グラフも整数です。たとえば、完全グラフ（辺のないグラフ）の補グラフは整数です。 2 つのグラフが整数であれば、それらの直積と強積も整数です。^{[ 2 ]}たとえば、2 つの完全グラフ（ルークのグラフ）の直積は整数です。^{[ 3 ]}同様に、任意の数の完全グラフの直積であるハイパーキューブグラフも整数です。$\displaystyle K_{2}}$は整数である。^{[ 2 ]}
• 正則積分グラフの線グラフは再び積分である。例えば、${\displaystyle K_{4}}$八面体グラフは整数であり、線グラフの補グラフとして${\displaystyle K_{5}}$ピーターセングラフは整数である。^{[ 2 ]}
• 3次対称グラフの中で、ユーティリティグラフ、ピーターセングラフ、ナウルグラフ、デサルググラフは整数グラフである。
• ヒグマン・シムズグラフ、ホール・ヤンコグラフ、クレブシュグラフ、ホフマン・シングルトングラフ、シュリカンデグラフ、ホフマングラフは整数グラフである。
• 正則グラフが周期的であるのは、それが整数グラフである場合に限る。
• 完全な状態転送を許容するウォーク正則グラフは、整数グラフである。
• 数独グラフ、つまり頂点が数独盤のマスを表し、辺が等しくないマスを表すグラフは、整数である。^{[ 4 ]}