ドマティック番号

グラフ理論において、グラフの支配分割とは、各V _{i が}Gの支配集合となるような、グラフを互いに素な集合、、...に分割することです。右の図はグラフの支配分割を示しています。ここで、支配集合は黄色の頂点で構成され、 は緑の頂点で構成され、 は青の頂点で構成されています。 ${\displaystyle G=(V,E)}$${\displaystyle V}$${\displaystyle V_{1}}$${\displaystyle V_{2}}$${\displaystyle V_{K}}$${\displaystyle V_{1}}$${\displaystyle V_{2}}$${\displaystyle V_{3}}$

ドマティック数は、ドマティック パーティションの最大サイズ、つまり、互いに素な支配セットの最大数です。図のグラフのドマティック数は 3 です。サイズ 3 のドマティック パーティションを示したので、ドマティック数が少なくとも3 であることは簡単にわかります。ドマティック数が最大 3 であることを確認するために、まず簡単な上限を確認します。

をグラフ の最小次数とします。 の支配数は最大で です。これを理解するために、次数 の頂点を考えます。が とその隣接点で構成されるとします。(1) 各支配集合には の頂点が少なくとも 1 つ含まれている必要がある(支配)、および (2) の各頂点は最大で 1 つの支配集合に含まれる(非結合) ことがわかっています。したがって、最大で 個の非結合支配集合が存在します。 ${\displaystyle \delta}$${\displaystyle G}$${\displaystyle G}$${\displaystyle \delta +1}$${\displaystyle v}$${\displaystyle \delta}$${\displaystyle N}$${\displaystyle v}$${\displaystyle V_{i}}$${\displaystyle N}$${\displaystyle N}$${\displaystyle V_{i}}$${\displaystyle |N|=\delta +1}$

図のグラフは最小次数 を持つため、そのドマティック数は最大 3 です。したがって、そのドマティック数はちょうど 3 であることが示されました。図は最大サイズのドマティック分割を示しています。 ${\displaystyle \delta =2}$

グラフに孤立した頂点がない場合（つまり、 ≥ 1）、ドマティック数は少なくとも 2 です。これを確認するには、(1)孤立した頂点がない場合、弱い 2 色付けはドマティック分割であり、(2) どのグラフにも弱い 2 色付けがあることに留意してください。あるいは、(1)最大独立集合は支配集合であり、(2) 孤立した頂点がない場合、最大独立集合の補集合も支配集合です。 ${\displaystyle \delta}$

右の図は、サイズ 2 のドマティック パーティションでもある弱い 2 色付けを示しています。暗いノードは支配セットであり、明るいノードは別の支配セットです (明るいノードは最大独立セットを形成します)。詳細については、 弱い色付けを参照してください。

サイズ 1 のドマティック パーティションを見つけるのは簡単です。 とします。サイズ 2 のドマティック パーティションを見つける (または存在しないことを判断する) のは簡単です。孤立したノードがあるかどうかを確認し、ない場合は弱い 2 色を見つけます。 ${\displaystyle V_{1}=V}$

しかし、最大サイズのドメイン分割を見つけることは計算上困難です。具体的には、ドメイン数問題と呼ばれる次の決定問題がNP 完全です。グラフと整数が与えられた場合、 のドメイン数が少なくとも であるかどうかを判断します。したがって、与えられたグラフのドメイン数を決定する問題はNP 困難であり、最大サイズのドメイン分割を見つける問題も NP 困難です。 ${\displaystyle G}$${\displaystyle K}$${\displaystyle G}$${\displaystyle K}$

対数近似保証を備えた多項式時間近似アルゴリズムがあり^[1]、つまり、サイズが最適値の係数以内であるドメインパーティションを見つけることが可能です。 ${\displaystyle O(\log |V|)}$

しかし、もっともらしい複雑性理論の仮定の下では、対数以下の近似係数を持つ多項式時間近似アルゴリズムは存在しない。^[1]より具体的には、近似係数が定数であるドメイン分割の多項式時間近似アルゴリズムは、NPのすべての問題がわずかに超多項式時間で解けることを意味します。 ${\displaystyle (1-\epsilon )\ln |V|}$${\displaystyle \epsilon >0}$${\displaystyle n^{O(\log \log n)}}$

ドマティックパーティション

頂点を互いに素な支配集合に分割します。支配数はそのような集合の最大数です。

頂点カラーリング

頂点を互いに素な独立集合に分割します。彩色数はそのような集合の最小数です。

クリーク分割

頂点を互いに素なクリークに分割します。補グラフの頂点の色付けに相当します。

エッジカラーリング

辺を互いに素なマッチングに分割します。辺彩色数は、そのような集合の最小数です。

G  = ( U  ∪  V ,  E ) を孤立ノードのない二部グラフとし、すべての辺が { u ,  v } ∈  E の形式をとり、u  ∈  Uかつv  ∈  Vであるとする。このとき、 { U ,  V } は頂点 2 彩色とサイズ 2 の支配分割の両方となり、集合UとV は独立した支配集合となる。 Gの彩色数はちょうど 2 であり、頂点 1 彩色は存在しない。Gの支配数は少なくとも 2 である。より大きな支配分割が存在することも可能であり、たとえば、任意のn ≥ 2に対する完全二部グラフ K _{n , n は} 支配数nを持つ。

• ゲーリー、マイケル R. ;ジョンソン、デビッド S. (1979)。コンピュータと扱いにくさ: NP 完全性理論ガイド。数学科学シリーズ (第 1 版)。ニューヨーク: WH フリーマン アンド カンパニー。ISBN 9780716710455. MR  0519066. OCLC  247570676.A1.1: GT3、190ページ。
• Cockayne, EJ; Hedetniemi, Stephen T. (1975)、「グラフにおける最適支配」、IEEE Transactions on Circuits and Systems、CAS-22 (11): 855–857、doi :10.1109/TCS.1975.1083994、MR  0384608。