K4の対辺を繋ぐグラフにしてみる

K_4の各辺を頂点にして、その完全マッチングの対に辺を引くという変換をおもいついて、やってみたら面白かった。

  • K_2 → 1頂点
  • K_3 → 3頂点、辺無し
  • K_4 → 6頂点、3本の辺
  • K_5 → petersenグラフ
  • K_6 → 正則グラフR^{6}_{15}
  • K_n → 正則グラフR^{\frac{(n-2)(n-3)}2}_{\frac{n(n-1)}2}, n \ge 2

Rの右肩が次数、右膝が頂点数。たぶんあってるとおもうんだけど。。。
n=1の場合もなんとなくイメージができて、頂点のない自己ループぽい(1正則、0頂点)のも趣きがある。
n=-1の場合は1頂点、6正則でK_4の変換後を回収しそうなのも面白い。実際3本の辺は同じクリークだし。

最大クリーク数もなんとなく関係性が見えて、変換後の辺(K_2)がK_4なのは明らかなので、およそ元のグラフの最大クリークの半分だろうとおもう(しっかり確認してないけど)。
普通のグラフでどんな性質あるんだろう?って感じ。

完全グラフでいえば、これはクネーザーグラフ K_{n:2}と一緒だな。