Domatiskt nummer

En domatisk partition

I grafteorin är en domatisk partition av en graf $G=(V,E)$ en partition av $V$ i disjunkta mängder $V_{1}$ , $V_{2}$ ,..., $V_{K}$ så att varje V _i är en dominerande mängd för G . Figuren till höger visar en domatisk partition av en graf; här består den dominerande mängden $V_{1}$ av de gula hörnen, $V_{2}$ består av de gröna hörnen och $V_{3}$ består av blå hörn.

Det domatiska numret är den maximala storleken på en domatisk partition, det vill säga det maximala antalet disjunkta dominerande uppsättningar. Grafen i figuren har domatiskt nummer 3. Det är lätt att se att det domatiska numret är minst 3 eftersom vi har presenterat en domatisk partition av storlek 3. För att se att domatiskt nummer är högst 3, granskar vi först en enkel övre gräns.

Övre gränser

Låt $\delta$ vara minimigraden för grafen $\displaystyle G}$ { . Det domatiska numret för $G$ är som mest $\delta +1$ . För att se detta, överväg en vertex $v$ av graden $\delta$ . Låt $N$ bestå av $v$ och dess grannar. Vi vet att (1) varje dominerande uppsättning Vi $\displaystyle V_{i}}$ innehålla minst en vertex i $N$ (domination), och (2) varje vertex i $N$ är ingår i högst en dominerande mängd $V_{i}$ (sönderdelning). Därför finns det högst $|N|=\delta +1$ disjunkta dominerande uppsättningar.

Grafen i figuren har minsta grad ${\displaystyle \delta =2} ,$ och därför är dess domatiska nummer högst 3. Därför har vi visat att dess domatiska nummer är exakt 3; figuren visar en domatisk partition med maximal storlek.

Nedre gränser

Svag 2-färgad

Om det inte finns någon isolerad vertex i grafen (det vill säga $\delta$ ≥ 1), så är det domatiska talet minst 2. För att se detta, notera att (1) en svag 2-färgning är en domatisk partitionera om det inte finns någon isolerad vertex, och (2) vilken graf som helst har en svag 2-färgning. Alternativt är (1) en maximal oberoende mängd en dominerande mängd, och (2) komplementet till en maximal oberoende mängd är också en dominerande mängd om det inte finns några isolerade hörn.

Figuren till höger visar en svag 2-färgning, som också är en domatisk partition av storlek 2: de mörka noderna är en dominerande uppsättning och de ljusa noderna är en annan dominerande uppsättning (de ljusa noderna bildar en maximalt oberoende uppsättning). Se svag färgning för mer information.

Beräkningskomplexitet

Att hitta en domatisk partition av storlek 1 är trivialt: låt $V_{1}=V$ . Att hitta en domatisk partition av storlek 2 (eller bestämma att den inte finns) är lätt: kontrollera om det finns isolerade noder, och om inte, hitta en svag 2-färgning.

Det är dock beräkningsmässigt svårt att hitta en domatisk partition med maximal storlek. Närmare bestämt är följande beslutsproblem , känt som det domatiska nummerproblemet , NP-komplett : givet en graf $G$ och ett heltal $K$ , bestäm om det domatiska numret för $G$ är minst $K$ . Därför är problemet med att bestämma det domatiska numret för en given graf NP-hårt , och problemet med att hitta en maximal storlek domatisk partition är också NP-svårt.

Det finns en polynom-tidsapproximationsalgoritm med en logaritmisk approximationsgaranti, det vill säga det är möjligt att hitta en domatisk partition vars storlek är inom en faktor $O(\log |V|)$ av det optimala.

Men under rimliga komplexitetsteoretiska antaganden finns det ingen polynom-tidsapproximationsalgoritm med en sublogaritmisk approximationsfaktor. Mer specifikt, en polynom-tidsapproximationsalgoritm för domatisk partition med approximationsfaktorn $(1-\epsilon )\ln |V|$ för en konstant $\epsilon >0$ skulle innebära att alla problem i NP kan lösas på något superpolynomisk tid $n^{O(\log \log n)}$ .

Jämförelse med liknande begrepp

Domatisk partition: Dela upp hörn i disjunkta dominerande uppsättningar. Det domatiska numret är det maximala antalet sådana uppsättningar.
Vertexfärgning: Dela upp hörn i osammanhängande oberoende uppsättningar . Det kromatiska antalet är det minsta antalet sådana uppsättningar.
Klickpartition: Dela upp hörn i osammanhängande klick . Lika med vertexfärgning i komplementgrafen .
Kantfärgning: Dela kanterna i osammanhängande matchningar . Det kromatiska kanttalet är det minsta antalet sådana uppsättningar.

Låt G = ( U ∪ V , E ) vara en tvådelad graf utan isolerade noder; alla kanter har formen { u , v } ∈ E med u ∈ U och v ∈ V . Då är { U , V } både en vertex 2-färgning och en domatisk partition av storlek 2; uppsättningarna U och V är oberoende dominerande uppsättningar. Det kromatiska talet för G är exakt 2; det finns ingen vertex 1-färgning. Det domatiska antalet G är minst 2. Det är möjligt att det finns en större domatisk partition; till exempel har den fullständiga tvådelade grafen K _{n , n} för alla n ≥ 2 domatiskt nummer n .

Anteckningar

Garey, Michael R .; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , W.H. Freeman , ISBN 0-7167-1045-5 . A1.1: GT3, sid. 190.
Cockayne, EJ; Hedetniemi, Stephen T. (1975), "Optimal domination in graphs", IEEE Transactions on Circuits and Systems , CAS-22 (11): 855–857, doi : 10.1109/TCS.1975.1083994 , MR 0384608 .