グラフの頻度分割

数学の一分野であるグラフ理論において、グラフ（単純グラフ）の頻度分割とは、頂点を次数によってグループ化した分割のことです。たとえば、以下の左側のグラフの次数列は (3, 3, 3, 2, 2, 1) であり、頻度分割は 6 = 3 + 2 + 1 です。これは、ある次数の頂点が 3 つ、別の次数の頂点が 2 つ、3 つ目の次数を持つ頂点が 1 つあることを示しています。以下の中央の二部グラフの次数列は (3, 2, 2, 2, 2, 2, 1, 1, 1) であり、頻度分割は 9 = 5 + 3 + 1 です。以下の右側のグラフの次数列は (3, 3, 3, 3, 3, 3, 2) であり、頻度分割は 7 = 6 + 1 です。

• 
  頻度分割 6 = 3 + 2 + 1 のグラフ。
• 
  頻度分割が 9 = 5 + 3 + 1 の二部グラフ。
• 
  頻度分割 7 = 6 + 1 のグラフ。

一般に、与えられた頻度分割を持つ非同型グラフは多数存在する。グラフとその補グラフは同じ頻度分割を持つ。整数p > 1の任意の分割p = f ₁ + f ₂ + ... + f _k （ p = 1 + 1 + 1 + ... + 1を除く）に対して、この分割を頻度分割とする（連結された）単純グラフが少なくとも1つ存在する。^[1]

さまざまなグラフ ファミリの頻度パーティションは完全に識別されますが、多くのグラフ ファミリの頻度パーティションは識別されません。

オイラーグラフの頻度分割

整数p > 1の頻度分割 p = f ₁ + f ₂ + ... + f _kの場合、そのグラフ次数列は ((d ₁ ) ^{f ₁} ,(d ₂ ) ^{f ₂} , (d ₃ ) ^{f ₃} , ..., (d _k ) ^{f _k} ) と表されます。ここで、次数 d _iは異なり、i  <  jに対してf _i ≥ f _jです。Bhat-Nayakら(1979) は、k 個の部分 (k ≤ の整数部) を持つ p の分割はオイラー グラフの頻度分割^[2]であり、その逆も成り立つことを示しました。 ${\displaystyle (p-1)/2}$

木、ハミルトングラフ、トーナメント、ハイパーグラフの頻度分割

木^[3] 、ハミルトングラフ^{[4] 、} 有向グラフ、トーナメント^[5]、k-一様ハイパーグラフ^[6]などのグラフ族の頻度分割が特徴付けられている 。

周波数分割における未解決の問題

次のグラフ ファミリの頻度パーティションはまだ特徴付けられていません。

• 折れ線グラフ
• 二部グラフ ^[7]

参考文献

1. Chinn, PZ (1971),グラフの頻度分割. グラフ理論の最近の動向, 数学講義ノート, 第186巻, ベルリン: Springer-Verlag, pp.  69– 70
2. Rao, Siddani Bhaskara; Bhat-Nayak, Vasanti N.; Naik, Ranjan N. (1979)、「オイラーグラフの頻度分割の特徴づけ」、グラフ理論シンポジウム論文集（インド統計研究所、カルカッタ、1976年）、ISI講義ノート、第4巻、Macmillan of India、ニューデリー、pp.  124– 137、MR  0553937また、Lecture Notes in Mathematics, Combinatorics and Graph Theory、Springer-Verlag、New York、Vol. 885 (1980)、p 500にも記載されています。
3. ラオ, TM (1974)、「グラフにおける頻度シーケンス」、組合せ理論ジャーナル、シリーズB、17 : 19– 21、doi : 10.1016/0095-8956(74)90042-2
4. * Bhat-Nayak, Vasanti N. ; Naik, Ranjan N. & Rao, SB (1977)、「周波数分割：強制的に汎巡回的かつ強制的に非ハミルトン的次数列」、離散数学、20 : 93–102、doi : 10.1016/0012-365x(77)90049-8
5. Alspach, B. & Reid, KB (1978)、「有向グラフとトーナメントにおける次数頻度」、Journal of Graph Theory、2 (3): 241– 249、doi :10.1002/jgt.3190020307
6. Bhat-Nayak, VN & Naik, RN (1985)、「k-uniformハイパーグラフの頻度分割」、Utilitas Math.、28 : 99–104
7. SB Rao、「潜在的p-グラフィックシーケンスと強制p-グラフィックシーケンスの理論の概説」、SB Rao編著『組合せ論とグラフ理論 数学講義ノート』第885巻（Springer、ベルリン、1981年）、417-440頁。

外部セクション

• Berge, C. (1989), Hypergraphs, Combinatorics of Finite sets , Amsterdam: North-Holland, ISBN 0-444-87489-5