クネーザーグラフ
n < 3kであるなら、クネーザーグラフは三角形を含まない。より一般的に、n ≥ 2k + 2 であればクネーザーグラフは常に長さ4の閉路を含むが、2k に近い値 n に対して、最も短い奇閉路は一定の長さを持たないことがある (Denley 1997)。
連結クネーザーグラフ KGn,k の直径 (distance (graph theory)) は ⌈ k − 1 n − 2 k ⌉ + 1 {\displaystyle \left\lceil {\frac {k-1}{n-2k}}\right\rceil +1} (Valencia-Pabon & Vera 2005)
である。
クネーザーグラフ KGn,k のグラフスペクトルは次のように与えられる:
j = 0 , . . . , k {\displaystyle j=0,...,k} に対し、固有値 λ j = ( − 1 ) j ( n − k − j k − j ) {\displaystyle \lambda _{j}=(-1)^{j}{\binom {n-k-j}{k-j}}} が得られる。ここで、その重複度は、 j > 0 {\displaystyle j>0} に対しては ( n j ) − ( n j − 1 ) {\displaystyle {\binom {n}{j}}-{\binom {n}{j-1}}} であり、 j = 0 {\displaystyle j=0} に対しては 1 となる。証明にはこの論文を参照されたい。