グラフの辞書式積

グラフ理論において、グラフGとグラフH の辞書式積または（グラフ）合成 G ∙ Hは、

• G ∙ Hの頂点集合は直積 V(G) × V(H)であり、
• 任意の2つの頂点( u、v )と( x、y )がG ∙ Hで隣接している場合、かつその場合のみ、uはGでxに隣接しているか、u = xかつvはHで yに隣接しています。

2 つのグラフのエッジ関係が順序関係である場合、それらの辞書式積のエッジ関係は対応する辞書式順序になります。

辞書式積は、フェリックス・ハウスドルフ(1914) によって初めて研究されました。ファイゲンバウムとシェーファー (1986) が示したように、グラフが辞書式積であるかどうかを認識する問題は、複雑さの点でグラフ同型性問題 と同等です。

辞書式積は一般に非可換です: G ∙ H ≠ H ∙ G。しかし、これは非結合和に関して分配法則を満たします: ( A + B ) ∙ C = A ∙ C + B ∙ C 。さらに、これは相補性に関して恒等式を満たします: C( G ∙ H ) = C( G ) ∙ C( H )。特に、2 つの自己相補グラフの辞書式積は自己相補的です。

辞書式積の 独立数は、その因数の独立数から簡単に計算できます (Geller & Stahl 1975)。

α( G ∙ H ) = α( G )α( H )。

辞書式積の クリーク数も乗法的である:

ω( G ∙ H ) = ω( G )ω( H )。

辞書式積の彩色数はGのb倍の彩色数に等しく、b はHの彩色数に等しい。

χ( G ∙ H ) = χ _b ( G )、ただしb = χ( H )。

2 つのグラフの辞書式積は、両方の因子が完全である場合にのみ 完全グラフになります (Ravindra & Parthasarathy 1977)。

• Feigenbaum, J.; Schäffer, AA (1986)、「複合グラフの認識はグラフ同型性のテストと同等である」、SIAM Journal on Computing、15 (2): 619–627、doi :10.1137/0215045、MR  0837609。
• ゲラー、D.; スタール、S. (1975)、「辞書式積の彩色数とその他の関数」、Journal of Combinatorial Theory、シリーズ B、19 : 87–95、doi :10.1016/0095-8956(75)90076-3、MR  0392645。
• ハウスドルフ、F. (1914)、グルンドチューゲ デア メンゲンレーレ、ライプツィヒ{{citation}}: CS1 メンテナンス: 場所が見つかりません 発行者 (リンク)
• イムリッチ、ウィルフリード、クラヴジャー、サンディ（2000）、プロダクトグラフ：構造と認識、Wiley、ISBN 0-471-37039-8
• ラビンドラ、G.; パルタサラシー、KR (1977)、「完全積グラフ」、離散数学、20 (2): 177–186、doi :10.1016/0012-365X(77)90056-5、hdl : 10338.dmlcz/102469、MR  0491304。

• Weisstein、Eric W.「グラフ辞書的積」。MathWorld。