Domatic number とは

グラフ理論では、グラフ G = ( V , E ) {\displaystyle G=(V,E)} のドミナントパーティションは V {\displaystyle V} を分割した集合 V 1 {\displaystyle V_{1}} V 2 {\displaystyle V_{2}} 、…、 V K {\displaystyle V_{K}} に分割し、各ViがGの支配的集合右側の図はグラフのドミナントパーティションを示しています。ここで支配的な集合 V 1 {\displaystyle V_{1}} は黄色の頂点で構成され、 V 2 {\displaystyle V_{2}} は緑の頂点で構成され、 V 3 {\displaystyle V_{3}} は青い頂点で構成されます。
ドミナント・ナンバーは、ドミナント・パーティションの最大サイズ、つまり、ディスジョイント・ドミネーティング・セットの最大数です。図のグラフは、3番のドミナントを示しています.3番のドミナント・パーティションを表示しているため、ドミナント・ナンバーが3以上であることは容易に分かります。ドミナント・ナンバーが3以下であることを確認するには、上界。