b'\n_START_ARTICLE_\nDominerende verzameling\n_START_PARAGRAPH_\nIn de grafentheorie is een dominerende verzameling van een graaf een deelverzameling van de knopen waarmee elke knoop buiten de dominerende verzameling verbonden is.\n_START_SECTION_\nDefinitie\n_START_PARAGRAPH_\nVoor een graaf  heet een deelverzameling  van de knopenverzameling  een dominerende verzameling, als elke knoop die geen element is van  verbonden is met minstens \xc3\xa9\xc3\xa9n element van _NEWLINE_Het dominantiegetal  van de graaf is het aantal knopen in de kleinst mogelijke dominerende verzameling voor\n_START_SECTION_\nTotale dominerende verzameling\n_START_PARAGRAPH_\nEen deelverzameling  van  is een totale dominerende verzameling wanneer elke knoop in  (dus ook de knopen in ) verbonden is met een element in  De minimale cardinaliteit van alle totale dominerende verzamelingen is het totale dominantiegetal  Een totale dominerende verzameling heeft geen ge\xc3\xafsoleerde knopen. In de figuur is enkel (c) een voorbeeld van een totale dominerende verzameling.\n_START_SECTION_\nVerband met knopenbedekking\n_START_PARAGRAPH_\nElke knopenbedekking is een dominerende verzameling. Het omgekeerde is niet waar; in de figuur hiernaast is geen enkele van de dominerende verzamelingen een knopenbedekking, want er zijn steeds kanten in de graaf die geen eindpunt in de dominerende verzameling hebben.\n_START_SECTION_\nComplexiteit\n_START_PARAGRAPH_\nHet beslissingsprobleem om voor een gegeven graaf  en gegeven natuurlijk getal  te beslissen of er een dominerende verzameling bestaat met hoogstens  knopen is NP-volledig.  is strikt kleiner dan het aantal knopen in de graaf._NEWLINE_Van meer belang is het probleem om een minimale dominerende verzameling, en dus het dominantiegetal, te vinden voor een graaf. Dit is een NP-moeilijk probleem.'