Conjunto dominante

En teoría de grafos , un conjunto dominante para un grafo G es un subconjunto D de sus vértices, tal que cualquier vértice de G está en D o tiene un vecino en D. El número de dominación γ( G ) es el número de vértices en el conjunto dominante más pequeño para G.

El problema del conjunto dominante consiste en comprobar si γ( G ) ≤ K para un grafo G dado y una entrada K ; es un problema de decisión clásico NP-completo en la teoría de la complejidad computacional . ^{[ 1 ]} Por lo tanto, se cree que puede que no exista un algoritmo eficiente que pueda calcular γ( G ) para todos los grafos G. Sin embargo, existen algoritmos de aproximación eficientes , así como algoritmos exactos eficientes para ciertas clases de grafos.

Los conjuntos dominantes son de interés práctico en diversas áreas. En redes inalámbricas , se utilizan para encontrar rutas eficientes en redes móviles ad hoc. También se han empleado en la generación de resúmenes de documentos y en el diseño de sistemas seguros para redes eléctricas .

Los conjuntos dominantes están estrechamente relacionados con los conjuntos independientes : un conjunto independiente es también un conjunto dominante si y solo si es un conjunto independiente maximal , por lo que cualquier conjunto independiente maximal en un grafo es necesariamente también un conjunto dominante mínimo.

Dado un grafo no dirigido G = ( V , E ) , un subconjunto de vértices${\displaystyle D\subseteq V}$se denomina conjunto dominante si para cada vértice${\displaystyle u\in V\setminus D}$, hay un vértice${\displaystyle v\in D}$de tal manera que${\displaystyle \{u,v\}\in E}$.

Cada grafo tiene al menos un conjunto dominante: si${\displaystyle D=V=}$el conjunto de todos los vértices, entonces por definición D es un conjunto dominante, ya que no hay ningún vértice${\displaystyle u\in V\setminus D}$Un desafío más interesante es encontrar conjuntos dominantes pequeños. El número de dominación de G se define como: ${\displaystyle \gamma (G):=\min\{|D|:D{\text{ is a dominating set of }}G\}}$.

El problema de la dominación se estudió desde la década de 1950, pero el ritmo de investigación sobre la dominación aumentó significativamente a mediados de la década de 1970. En 1972, Richard Karp demostró que el problema de la cobertura de conjuntos es NP-completo . Esto tuvo implicaciones inmediatas para el problema del conjunto dominante, ya que existen biyecciones directas de vértice a conjunto y de arista a intersección no disjunta entre ambos problemas. Esto demostró que el problema del conjunto dominante también es NP-completo . ^{[ 2 ]}

El problema de cobertura de conjuntos es un problema NP-difícil bien conocido ; la versión de decisión de la cobertura de conjuntos fue uno de los 21 problemas NP-completos de Karp . Existen dos reducciones L de tiempo polinomial entre el problema del conjunto dominante mínimo y el problema de cobertura de conjuntos . ^{[ 3 ]} Estas reducciones ( véase más adelante ) muestran que un algoritmo eficiente para el problema del conjunto dominante mínimo proporcionaría un algoritmo eficiente para el problema de cobertura de conjuntos, y viceversa. Además, las reducciones preservan la razón de aproximación : para cualquier α, un algoritmo de aproximación α de tiempo polinomial para conjuntos dominantes mínimos proporcionaría un algoritmo de aproximación α de tiempo polinomial para el problema de cobertura de conjuntos, y viceversa. Ambos problemas son, de hecho, Log-APX-completos . ^{[ 4 ]}

La aproximabilidad de la cobertura de conjuntos también se comprende bien: se puede encontrar un factor de aproximación logarítmico utilizando un algoritmo voraz simple , y encontrar un factor de aproximación sublogarítmico es NP-difícil. Más específicamente, el algoritmo voraz proporciona una aproximación de factor 1 + log | V | de un conjunto dominante mínimo, y ningún algoritmo de tiempo polinomial puede lograr un factor de aproximación mejor que c log | V | para algún c > 0 a menos que P = NP . ^{[ 5 ]}

L-reducciones

Las siguientes dos reducciones muestran que el problema del conjunto dominante mínimo y el problema de la cobertura de conjuntos son equivalentes bajo reducciones L : dada una instancia de un problema, podemos construir una instancia equivalente del otro problema. ^{[ 3 ]}

Desde dominar el set hasta cubrir el set

Dado un grafo G = ( V , E ) con V = {1, 2, ..., n }, construya una instancia de cobertura de conjuntos ( U , S ) de la siguiente manera: el universo U es V , y la familia de subconjuntos es S = { S ₁ , S ₂ , ..., S _n } tal que S _v consiste en el vértice v y todos los vértices adyacentes a v en G .

Ahora bien, si D es un conjunto dominante para G , entonces C = { S _v  : v ∈ D } es una solución factible del problema de cobertura de conjuntos, con | C | = | D | . Recíprocamente, si C = { S _v  : v ∈ D } es una solución factible del problema de cobertura de conjuntos, entonces D es un conjunto dominante para G , con | D | = | C | .

Por lo tanto, el tamaño de un conjunto dominante mínimo para G es igual al tamaño de una cobertura de conjuntos mínima para ( U , S ) . Además, existe un algoritmo sencillo que asigna un conjunto dominante a una cobertura de conjuntos del mismo tamaño y viceversa. En particular, un algoritmo de aproximación α eficiente para la cobertura de conjuntos proporciona un algoritmo de aproximación α eficiente para conjuntos dominantes mínimos.

Por ejemplo, dado el grafo G que se muestra a la derecha, construimos una instancia de cobertura de conjuntos con el universo U = {1, 2, ..., 6} y los subconjuntos S ₁ = {1, 2, 5}, S ₂ = {1, 2, 3, 5}, S ₃ = {2, 3, 4, 6}, S ₄ = {3, 4}, S ₅ = {1, 2, 5, 6} y S ₆ = {3, 5, 6}. En este ejemplo, D = {3, 5} es un conjunto dominante para G ; esto corresponde a la cobertura de conjuntos C = { S ₃ , S ₅ }. Por ejemplo, el vértice 4 ∈ V está dominado por el vértice 3 ∈ D , y el elemento 4 ∈ U está contenido en el conjunto S ₃ ∈ C.

Desde cubrir el set hasta dominar el set

Sea ( S , U ) una instancia del problema de cobertura de conjuntos con el universo U y la familia de subconjuntos S = { S _i  : i ∈ I }; suponemos que U y el conjunto de índices I son disjuntos. Construimos un grafo G = ( V , E ) de la siguiente manera: el conjunto de vértices es V = I ∪ U , hay una arista { i , j } ∈ E entre cada par i , j ∈ I , y también hay una arista { i , u } para cada i ∈ I y u ∈ S _i . Es decir, G es un grafo dividido : I es una camarilla y U es un conjunto independiente .

Ahora bien, si C = { S _i  : i ∈ D } es una solución factible del problema de cobertura de conjuntos para algún subconjunto D ⊆ I , entonces D es un conjunto dominante para G , con | D | = | C | : Primero, para cada u ∈ U hay un i ∈ D tal que u ∈ S _i , y por construcción, u e i son adyacentes en G ; por lo tanto , u está dominado por i . Segundo, dado que D debe ser no vacío, cada i ∈ I es adyacente a un vértice en D .

Por el contrario, sea D un conjunto dominante para G. Entonces es posible construir otro conjunto dominante X tal que | X | ≤ | D | y X ⊆ I : simplemente reemplazamos cada u ∈ D ∩ U por un vecino i ∈ I de u . Entonces C = { S _i  : i ∈ X } es una solución factible del problema de cobertura de conjuntos, con | C | = | X | ≤ | D | .

La ilustración de la derecha muestra la construcción para U = { a , b , c , d , e }, I = {1, 2, 3, 4}, S ₁ = { a , b , c }, S ₂ = { a , b }, S ₃ = { b , c , d } y S ₄ = { c , d , e }.

En este ejemplo, C = { S ₁ , S ₄ } es una cobertura de conjuntos; esto corresponde al conjunto dominante D = {1, 4}.

D = { a , 3, 4} es otro conjunto dominante para el grafo G . Dado D , podemos construir un conjunto dominante X = {1, 3, 4} que no es mayor que D y que es un subconjunto de I . El conjunto dominante X corresponde a la cobertura de conjuntos C = { S ₁ , S ₃ , S ₄ }.

Un conjunto dominante independiente es un conjunto dominante que también es un conjunto independiente , o equivalentemente, un conjunto independiente maximal . El número de dominación independiente${\displaystyle i(G)}$es el tamaño mínimo de un conjunto dominante independiente de G. Dado que el mínimo se toma sobre menos conjuntos,${\displaystyle \gamma (G)\leq i(G)}$para todos los grafos G , y la desigualdad puede ser estricta. La igualdad se cumple para grafos sin garras ; ^{[ 15 ]} dado que todo grafo de línea está libre de garras, se deduce que el emparejamiento máximo mínimo y el conjunto dominante de aristas mínimo de cualquier grafo tienen el mismo tamaño.

Un conjunto dominante de independencia de un grafo${\displaystyle G}$es un conjunto que domina a todos los conjuntos independientes de${\displaystyle G}$. El número de dominación de la independencia${\displaystyle i\gamma (G)}$es el máximo, sobre todos los conjuntos independientes${\displaystyle A}$de${\displaystyle G}$, del conjunto más pequeño dominante${\displaystyle A}$. ^{[ 16 ]} Dominar solo conjuntos independientes requiere potencialmente menos vértices que dominar todos los vértices, por lo que${\displaystyle i\gamma (G)\leq \gamma (G)}$para todos los gráficos${\displaystyle G}$y la proporción${\displaystyle \gamma (G)/i\gamma (G)}$puede ser arbitrariamente grande. ^{[ 16 ]}

Un conjunto dominante conexo es un conjunto dominante que también es conexo . Si${\displaystyle S}$es un conjunto dominante conectado, se puede formar un árbol de expansión de${\displaystyle G}$en el cual${\displaystyle S}$forma el conjunto de vértices no hoja del árbol; por el contrario, si${\displaystyle T}$es cualquier árbol de expansión en un grafo con más de dos vértices, los vértices no hoja de${\displaystyle T}$forman un conjunto dominante conectado. Por lo tanto, encontrar conjuntos dominantes conectados mínimos es equivalente a encontrar árboles de expansión con el máximo número posible de hojas.

Un conjunto dominante total es un conjunto de vértices tal que todos los vértices del grafo, incluidos los vértices del propio conjunto dominante, tienen un vecino en el conjunto dominante. ^{[ 17 ]} Es decir: para cada vértice${\displaystyle u\in V}$, hay un vértice${\displaystyle v\in D}$de tal manera que${\displaystyle \{u,v\}\in E}$La figura (c) anterior muestra un conjunto dominante que es un conjunto dominante conectado y un conjunto dominante total; los ejemplos de las figuras (a) y (b) no son ninguno de los dos. A diferencia de un conjunto dominante simple, un conjunto dominante total puede no existir. Por ejemplo, un grafo con uno o más vértices y ninguna arista no tiene un conjunto dominante total. El número de dominación total${\displaystyle \gamma ^{\text{total}}(G)}$se define como el tamaño mínimo de un conjunto dominante total de G ; obviamente,${\displaystyle \gamma ^{\text{total}}(G)\geq \gamma (G)}$.

Un conjunto de aristas dominante es un conjunto de aristas (pares de vértices) cuya unión es un conjunto dominante; dicho conjunto puede no existir (por ejemplo, un grafo con uno o más vértices y ninguna arista no lo tiene). Si existe, entonces la unión de todas sus aristas es un conjunto dominante total. Por lo tanto, el tamaño mínimo de un conjunto de aristas dominante es al menos${\displaystyle \gamma ^{\text{total}}(G)/2}$.

Por el contrario, un conjunto dominado por aristas es un conjunto${\displaystyle D}$de aristas, de tal manera que cada arista que no esté en${\displaystyle D}$es adyacente al menos a una arista en${\displaystyle D}$; dicho conjunto siempre existe (por ejemplo, el conjunto de todas las aristas es un conjunto dominado por aristas).

Un conjunto k -dominante es un conjunto de vértices tal que cada vértice que no está en el conjunto tiene al menos k vecinos en el conjunto (un conjunto dominante estándar es un conjunto 1-dominante). De manera similar, un conjunto k -dominante de tuplas es un conjunto de vértices tal que cada vértice en el grafo tiene al menos k vecinos en el conjunto (un conjunto dominante total es un conjunto 1-dominante de tuplas). Una aproximación (1 +  log n ) de un conjunto k - dominante de tuplas mínimo se puede encontrar en tiempo polinomial. ^{[ 18 ]} Todo grafo admite un conjunto k- dominante (por ejemplo, el conjunto de todos los vértices); pero solo los grafos con grado mínimo k − 1 admiten un conjunto k -dominante de tuplas. Sin embargo, incluso si el grafo admite un conjunto k -dominante de tuplas, un conjunto k -dominante de tuplas mínimo puede ser casi k veces más grande que un conjunto k -dominante mínimo para el mismo grafo; ^{[ 19 ]} Una aproximación (1,7 + log Δ) de un conjunto k -dominante mínimo también se puede encontrar en tiempo polinomial.

Un conjunto dominante fraccionario se define a partir de una función dominante fraccionaria , una función${\displaystyle f:V(G)\to [0,1]}$de tal manera que para cada vértice${\displaystyle v\in V}$, la suma de${\displaystyle f}$sobre el barrio cerrado${\displaystyle N[v]}$es al menos 1. ^{[ 20 ]} El número de dominación fraccionaria${\displaystyle \gamma _{f}(G)}$es el peso total mínimo (suma de todos los valores de los vértices) de dicha función y satisface${\displaystyle \gamma _{f}(G)\leq \gamma (G)}$. Para un${\displaystyle k}$- gráfico regular con${\displaystyle n}$vértices (${\displaystyle k\geq 1}$), el número de dominación fraccionaria es igual a${\displaystyle n/(k+1)}$.

Un conjunto dominado por estrellas es un subconjunto${\displaystyle D}$de${\displaystyle V}$de tal manera que, para cada vértice${\displaystyle v}$en${\displaystyle V}$, la estrella de${\displaystyle v}$(el conjunto de aristas adyacentes a${\displaystyle v}$) interseca la estrella de algún vértice en${\displaystyle D}$. Claramente, si${\displaystyle G}$Si tiene vértices aislados, entonces no tiene conjuntos dominados por estrellas (ya que la estrella de vértices aislados está vacía).${\displaystyle G}$Si no tiene vértices aislados, entonces todo conjunto dominante es un conjunto estrellado dominante y viceversa. La distinción entre dominación estrellada y dominación usual es más sustancial cuando se consideran sus variantes fraccionarias. ^{[ 21 ]}

Una partición domática es una partición de los vértices en conjuntos dominantes disjuntos. El número domático es el tamaño máximo de una partición domática.

Un conjunto dominante eterno es una versión dinámica de dominación en la que un vértice${\displaystyle v}$en el conjunto dominante${\displaystyle D}$es elegido y reemplazado por un vecino${\displaystyle u}$(${\displaystyle u}$no está en${\displaystyle D}$) de tal manera que el modificado${\displaystyle D}$También es un conjunto dominante y este proceso puede repetirse sobre cualquier secuencia infinita de elecciones de vértices. ${\displaystyle v}$.

Un conjunto dominante eficiente (también llamado conjunto ed o conjunto dominante perfecto independiente ^{[ 22 ]} ) es un conjunto dominante con la propiedad adicional de que cada vértice del grafo está dominado por exactamente un vértice del conjunto. ^{[ 23 ]}

Un conjunto romano dominante se define mediante una función romana dominante , que asigna a cada vértice un valor de${\displaystyle \{0,1,2\}}$de tal manera que cada vértice con valor 0 sea adyacente a al menos un vértice con valor 2. El número de dominación romana${\displaystyle \gamma _{R}(G)}$es la suma mínima de todos los valores de los vértices sobre todas esas funciones. El concepto está inspirado en una estrategia defensiva del Imperio Romano, donde los vértices representan ciudades y los valores representan legiones estacionadas. Para cualquier grafo${\displaystyle G}$,${\displaystyle \gamma (G)\leq \gamma _{R}(G)\leq 2\gamma (G)}$, con el límite inferior alcanzado únicamente por el grafo vacío . ^{[ 24 ]}

Un conjunto dominante global es un conjunto dominante de un grafo.${\displaystyle G}$que también es un conjunto dominante del grafo complementario${\displaystyle {\overline {G}}}$. El número de dominación global${\displaystyle \gamma _{g}(G)}$es la cardinalidad mínima de un conjunto dominante global. De manera equivalente, un conjunto dominante${\displaystyle S}$es un conjunto dominante global si y solo si para cada vértice${\displaystyle v\in V-S}$, existe un vértice${\displaystyle u\in S}$de tal manera que${\displaystyle u}$no es adyacente a${\displaystyle v}$. Por definición,${\displaystyle \gamma _{g}(G)=\gamma _{g}{\big (}{\overline {G}}{\big )}}$y${\displaystyle \gamma (G)\leq \gamma _{g}(G)}$Para un gráfico${\displaystyle G}$con${\displaystyle p}$vértices,${\displaystyle \gamma _{g}(G)=p}$si y solo si${\displaystyle G=K_{p}}$o${\displaystyle G={\overline {K_{p}}}}$. ^{[ 25 ]}

Un conjunto dominante certificado es un conjunto dominante en el que cada vértice del conjunto tiene cero o al menos dos vecinos fuera del conjunto. ^{[ 26 ]} El número de dominación certificado${\displaystyle \gamma _{\text{cer}}(G)}$es el tamaño mínimo de un conjunto dominante certificado. Claramente,${\displaystyle \gamma _{\text{cer}}(G)\geq \gamma (G)}$y la igualdad se cumple siempre que el grafo no tenga ningún vértice de soporte débil (en particular, cuando${\displaystyle \delta (G)\geq 2}$). Para un grafo conectado,${\displaystyle \gamma _{\text{cer}}(G)\leq 2\gamma (G)}$.

Un conjunto dominante emparejado de un grafo${\displaystyle G=(V,E)}$es un conjunto dominante${\displaystyle S}$de vértices tales que el subgrafo inducido${\displaystyle G[S]}$contiene al menos un emparejamiento perfecto . ^{[ 27 ]} El número de dominación emparejada${\displaystyle \gamma _{p}(G)}$es la cardinalidad mínima de un conjunto dominante emparejado de${\displaystyle G}$El concepto modela una situación en la que se colocan guardianes en los vértices de un grafo para dominar (proteger) todos los vértices, con la restricción adicional de que a cada guardián se le asigna otro guardián adyacente como respaldo.

Otras variantes incluyen

• conjunto dominante restringido, ^{[ 28 ]}
• conjunto dominante seguro, ^{[ 29 ]}
• conjunto dominante triplemente conectado, ^{[ 30 ]}
• conjunto dominante firmado, ^{[ 31 ]}
• menos el conjunto dominante, ^{[ 32 ]} y
• Conjunto dominante amistoso. ^{[ 33 ]}

• La conjetura de Vizing relaciona el número de dominación de un producto cartesiano de grafos con el número de dominación de sus factores.
• Problema de la cubierta del conjunto
• Número de bondage
• No bloqueador : el complemento de un conjunto dominante.
• Vértice universal : un conjunto dominante de un solo vértice.

• Aharoni, Ron; Berger, Eli; Ziv, Ran (1 de mayo de 2007). "Sistemas independientes de representantes en gráficos ponderados". Combinatoria . 27 (3): 253– 267. doi : 10.1007/s00493-007-2086-y . ISSN 1439-6912 . S2CID 43510417 .  
• Alber, Jochen; Fellows, Michael R ; Niedermeier, Rolf (2004), "Reducción de datos en tiempo polinomial para el conjunto dominante", Journal of the ACM , 51 (3): 363–384 , arXiv : cs/0207066 , doi : 10.1145/990308.990309 , S2CID 488501 .
• Allan, Robert B.; Laskar, Renu (1978), "Sobre la dominación y los números de dominación independientes de un grafo", Matemáticas Discretas , 23 (2): 73– 76, doi : 10.1016/0012-365X(78)90105-X.
• Bange, DW; Barkauskas, AE; Slater, PJ (1988). "Conjuntos dominantes eficientes en grafos". Aplicaciones de las matemáticas discretas . Filadelfia: SIAM. págs. 189–199 . 
• Brandstädt, Andreas; Leitert, Arne; Rautenbach, Dieter (2012). «Conjuntos dominantes y de dominancia de aristas eficientes para grafos e hipergrafos». Algoritmos y computación . Notas de clase en ciencias de la computación. Vol.  7676. Berlín, Heidelberg: Springer. pp. 267–277 . arXiv : 1207.0953 . doi : 10.1007/978-3-642-35261-4_30 . ISBN  978-3-642-35261-4.
• Cabahug Jr., IS; Eballe, RG; Fernandez, RT (2025). "Dominación amistosa en grafos" . European Journal of Pure & Applied Mathematics . 18 (4): 1– 15. doi : 10.29020/nybg.ejpam.v18i4.6326 .
• Cockayne, EJ; Dreyer, PA; Hedetniemi, SM; Hedetniemi, ST (2004). "Dominación romana en grafos". Matemáticas Discretas . 278 ( 1– 3): 11– 22. doi : 10.1016/j.disc.2003.06.004 .
• Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek ; Woeginger, Gerhard (2000), "Conjunto dominante mínimo", Compendio de problemas de optimización de NP.
• Dehne, Frank; Fellows, Michael; Fernau, Henning; Prieto, Elena ; Rosamond, Frances (2006), "Nonblocker: Algoritmos parametrizados para el conjunto dominante mínimo" (PDF) , SOFSEM 2006: 32.ª Conferencia sobre Tendencias Actuales en Teoría y Práctica de la Informática, Merin, República Checa, 21-27 de enero de 2006, Actas , Lecture Notes in Computer Science, vol.  3831, Springer, pp. 237–245 , doi : 10.1007/11611257_21 , ISBN  978-3-540-31198-0.
• Dettlaff, Magda; Lemanska, Magdalena; Topp, Jerzy; Ziemann, Radosław; Żyliński, Paweł (2020). «Dominación certificada» . AKCE Revista Internacional de Gráficos y Combinatoria . 17 (1): 86– 97. doi : 10.1016/j.akcej.2018.09.004 . ISSN 0972-8600 . 
• Domke, Gayla S.; Hattingh, Johannes H.; Hedetniemi, Stephen T.; Laskar, Renu C.; Markus, Lisa R. (1999). "Dominación restringida en grafos". Matemáticas Discretas . 203 ( 1– 3): 61– 69. doi : 10.1016/S0012-365X(99)00016-3 . ISSN 0012-365X . 
• Escoffier, Bruno; Paschos, Vangelis Th. (2006), "Completitud en clases de aproximación más allá de APX" (PDF) , Theoretical Computer Science , 359 ( 1–3 ): 369–377 , doi : 10.1016/j.tcs.2006.05.023
• Faudree, Ralph ; Flandrin, Evelyne; Ryjáček, Zdeněk (1997), "Grafos sin garras: una revisión", Matemáticas Discretas , 164 ( 1–3 ): 87–147 , doi : 10.1016/S0012-365X(96)00045-3 , MR 1432221 .
• Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter (2009), "Un enfoque de medición y conquista para el análisis de algoritmos exactos", Journal of the ACM , 56 (5): 25:1–32, doi : 10.1145/1552285.1552286 , S2CID 1186651 .
• Fomin, Fedor V.; Grandoni, Fabrizio; Pyatkin, Artem; Stepanov, Alexey (2008), "Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications", ACM Transactions on Algorithms , 5 (1): 9:1–17, doi : 10.1145/1435375.1435384 , S2CID 2489447 .
• Fomin, Fedor V.; Thilikos, Dimitrios M. (2006), "Conjuntos dominantes en grafos planares: ancho de rama y aceleración exponencial", SIAM Journal on Computing , 36 (2): 281, doi : 10.1137/S0097539702419649 , hdl : 2117/97398 , S2CID 5232238 .
• Förster, Klaus-Tycho. (2013), "Aproximación de la dominación tolerante a fallos en grafos generales", Actas del Décimo Taller sobre Algoritmos Analíticos y Combinatorios ANALCO , SIAM, pp. 25–32 , doi : 10.1137/1.9781611973037.4 , ISBN  978-1-61197-254-2.
• Garey, Michael R.; Johnson , David S. (1979). Computadoras e intratabilidad: una guía a la teoría de la NP-completitud . Serie de libros en ciencias matemáticas (1.ª  ed.). Nueva York: WH Freeman and Company . ISBN 9780716710455. MR 0519066 . OCLC 247570676 .  , pág.  190, problema GT2.
• Haas, Ruth; Wexler, Thomas B. (2004). "Números de dominación con signo de un grafo y su complemento". Matemáticas Discretas . 283 ( 1– 3): 87– 92. doi : 10.1016/j.disc.2004.01.007 . ISSN 0012-365X . 
• Haynes, Teresa W.; Hedetniemi, Stephen T.; Slater, Peter J. (1998). Fundamentos de dominación en grafos . Marcel Dekker. pp. 261–262 . ISBN  9780429157769.
• Haynes, Teresa W.; Slater, Peter J. (1998). "Dominación por pares en grafos". Networks . 32 (3): 199– 206. doi : 10.1002/(SICI)1097-0037(199810)32:3 < 199::AID-NET4 > 3.0.CO ; 2-F . ISSN 0028-3045 . 
• Hedetniemi, ST; Laskar, RC (1990), "Bibliografía sobre dominación en grafos y algunas definiciones básicas de parámetros de dominación", Matemáticas Discretas , 86 ( 1–3 ): 257–277 , doi : 10.1016/0012-365X(90)90365-O.
• Kang, L.; Shan, E. (2020). «Funciones dominantes con signo y negativas en grafos». En Haynes, TW; Hedetniemi, ST; Henning, MA (eds.). Temas de dominación en grafos . Developments in Mathematics. Vol.  64. Cham: Springer. doi : 10.1007/978-3-030-51117-3_9 . ISBN 978-3-030-51117-3.
• Kann, Viggo (1992), Sobre la aproximabilidad de problemas de optimización NP-completos (PDF) . Tesis doctoral, Departamento de Análisis Numérico y Ciencias de la Computación, Real Instituto de Tecnología , Estocolmo.{{citation}}: CS1 maint: postscript ( enlace ) .
• Klasing, Ralf; Laforest, Christian (2004), "Resultados de dureza y algoritmos de aproximación de la dominación de k-tuplas en grafos", Information Processing Letters , 89 (2): 75–83 , doi : 10.1016/j.ipl.2003.10.004.
• Mahadevan, G; Avadayappan, S; Joseph, JP; Subramanian, T (2012). "Número de dominación triplemente conexo de un grafo". Revista Internacional de Combinatoria Matemática . 3 : 93–104 .
• Merouane, Houcine Boumediene; Chellali, Mustapha (2015). "Sobre la dominación segura en grafos". Information Processing Letters . 115 (10): 786– 790. doi : 10.1016/j.ipl.2015.05.006 . ISSN 0020-0190 . 
• Meshulam, Roy (1 de mayo de 2003). "Números de dominación y homología" . Journal of Combinatorial Theory, Serie A. 102 ( 2): 321– 330. doi : 10.1016/S0097-3165(03)00045-1 . ISSN 0097-3165 . 
• Papadimitriou, Christos H.; Yannakakis, Mihailis (1991), "Optimization, Approximation, and Complexity Classes", Journal of Computer and System Sciences , 43 (3): 425– 440, doi : 10.1016/0022-0000(91)90023-X
• Parekh, Abhay K. (1991), "Análisis de una heurística voraz para encontrar conjuntos dominantes pequeños en grafos", Information Processing Letters , 39 (5): 237– 240, doi : 10.1016/0020-0190(91)90021-9 , hdl : 1721.1/1201
• Raz, R. ; Safra, S. (1997), "Una prueba de bajo grado con probabilidad de error subconstante y caracterización PCP de NP con probabilidad de error subconstante", Actas del 29.º Simposio Anual de la ACM sobre Teoría de la Computación , ACM, pp. 475–484 , doi : 10.1145/258533.258641 , ISBN  0-89791-888-6, S2CID 15457604 .
• Sampathkumar, E. (1989). "El número de dominación global de un grafo" . Journal of Mathematical and Physical Sciences . 23 (5): 377– 385.
• Takamizawa, K.; Nishizeki, T .; Saito, N. (1982), "Computabilidad en tiempo lineal de problemas combinatorios en grafos serie-paralelo", Journal of the ACM , 29 (3): 623– 641, doi : 10.1145/322326.322328 , S2CID 16082154 .
• Telle, Jan Arne; Villanger, Yngve (2012), "Algoritmos FPT para la dominación en grafos libres de bicliques", en Epstein, Leah; Ferragina, Paolo (eds.), Algorithms – ESA 2012: 20.º Simposio Europeo Anual, Ljubljana, Eslovenia, 10-12 de septiembre de 2012, Actas , Lecture Notes in Computer Science , vol.  7501, Springer, pp. 802-812 , doi : 10.1007/978-3-642-33090-2_69 , ISBN  978-3-642-33089-6.
• van Rooij, JMM; Nederlof, J.; van Dijk, TC (2009), "La inclusión/exclusión se une a la medida y la conquista: algoritmos exactos para contar conjuntos dominantes", Proc. 17º Simposio Europeo Anual sobre Algoritmos, ESA 2009 , Lecture Notes in Computer Science, vol.  5757, Springer, págs. 554–565 , doi : 10.1007/978-3-642-04128-0_50 , ISBN  978-3-642-04127-3.

• Grandoni, F. (2006), "Una nota sobre la complejidad del conjunto dominante mínimo", Journal of Discrete Algorithms , 4 (2): 209– 214, CiteSeerX 10.1.1.108.3223 , doi : 10.1016/j.jda.2005.03.002 .
• Guha, S.; Khuller, S. (1998), "Algoritmos de aproximación para conjuntos dominantes conectados" (PDF) , Algorithmica , 20 (4): 374–387 , doi : 10.1007/PL00009201 , hdl : 1903/830 , S2CID 1249122 .
• Haynes, Teresa W.; Hedetniemi, Stephen; Slater, Peter (1998a), Fundamentos de dominación en grafos , Marcel Dekker, ISBN 0-8247-0033-3, OCLC 37903553 .
• Haynes, Teresa W.; Hedetniemi, Stephen; Slater, Peter (1998b), Dominación en grafos: temas avanzados , Marcel Dekker, ISBN 0-8247-0034-1, OCLC 38201061 .
• West, Douglas B. (2001), Introducción a la teoría de grafos (2.ª  ed.), Pearson Education.