Loading article…
数学において、k-超同次グラフとは、最大でk個の頂点を持つ2つの誘導サブグラフ間のすべての同型性がグラフ全体の自己同型性に拡張できるグラフである。k-同次グラフは同じ性質の弱められたバージョンに従い、2つの誘導サブグラフ間のすべての同型性は、1つのサブグラフを他のサブグラフにマッピングするグラフ全体の自己同型性の存在を意味する（ただし、必ずしも与えられた同型性を拡張するわけではない）。[1]
同次グラフは、任意のkに対してk同次であるグラフ、または同等に任意のkに対してk超同次であるグラフです。[1]これは同次モデルの特殊なケースです。
分類
唯一の有限同次グラフは、同型完全グラフの非結合和集合から形成されるクラスターグラフ mK n、mK nの補グラフとして形成されるトゥラングラフ、3×3ルークグラフ、および5サイクルである。[2]
可算無限の同次グラフは、同型完全グラフ（各完全グラフのサイズ、完全グラフの数、またはその両方が可算無限である）の互いに素な和、それらの補グラフ、ヘンソングラフとその補グラフ、およびラドグラフのみです。[3]
グラフが 5 超同次であれば、すべてのkに対して超同次である。4超同次だが 5 超同次ではない連結グラフは、シュレーフリグラフとその補グラフの2 つだけである。証明は有限単純群の分類に依存している。[4]
バリエーション
グラフが連結同次グラフであるとは、連結された2つの誘導部分グラフ間の同型性がグラフ全体の自己同型性に拡張できる場合を言う。同次グラフに加えて、有限連結連結同次グラフには、すべてのサイクルグラフ、すべてのスクエアルークグラフ、ピーターセングラフ、および5正則クレプシュグラフが含まれる。[5]
注記
- ^ ab Ronse (1978)より。
- ^ ガーディナー（1976年）。
- ^ ラクラン＆ウッドロー（1980年）。
- ^ Buczak (1980); Cameron (1980); Devillers (2002).
- ^ ガーディナー（1978）；グレイ＆マクファーソン（2010）
参考文献
- Buczak, JMJ (1980)、有限群論、博士論文、オックスフォード大学Devillers (2002) より引用。
- キャメロン、ピーター・ジェフソン（1980）、「6推移グラフ」、組合せ理論ジャーナル、シリーズB、28：168-179、doi：10.1016/0095-8956（80）90063-5Devillers (2002) より引用。
- デビラー、アリス (2002)、均質および超均質構造の分類、博士論文、ブリュッセル自由大学。
- ガーディナー、A. (1976)、「同次グラフ」、組合せ理論ジャーナル、シリーズ B、20 (1): 94–102、doi :10.1016/0095-8956(76)90072-1、MR 0419293。
- ガーディナー、A. (1978)、「グラフにおける同質性条件」、組合せ理論ジャーナル、シリーズ B、24 (3): 301–310、doi : 10.1016/0095-8956(78)90048-5、MR 0496449。
- グレイ、R.; マクファーソン、D. (2010)、「可算連結同次グラフ」、Journal of Combinatorial Theory、シリーズ B、100 (2): 97–118、doi : 10.1016/j.jctb.2009.04.002、MR 2595694。
- ラクラン、AH; ウッドロー、ロバート E. (1980)、「可算超同次無向グラフ」、アメリカ数学会誌、262 (1): 51–94、doi : 10.2307/1999974、MR 0583847。
- ロンセ、クリスチャン (1978)、「同次グラフについて」、ロンドン数学会誌、第 2 シリーズ、17 (3): 375–379、doi :10.1112/jlms/s2-17.3.375、MR 0500619。