En la teoría de grafos , un área de las matemáticas, un gráfico sin garras es un gráfico que no tiene garras como subgrafo inducido .
Una garra es otro nombre para el gráfico bipartito completo K 1,3 (es decir, un gráfico de estrella con tres bordes, tres hojas y un vértice central). Un gráfico sin garras es un gráfico en el que ningún subgráfico inducido es una garra; es decir, cualquier subconjunto de cuatro vértices tiene más que solo tres bordes que los conectan en este patrón. De manera equivalente, una gráfica sin garras es una gráfica en la que la vecindad de cualquier vértice es el complemento de una gráfica sin triángulos .
Los gráficos sin garras se estudiaron inicialmente como una generalización de los gráficos de líneas y obtuvieron una motivación adicional a través de tres descubrimientos clave sobre ellos: el hecho de que todos los gráficos conectados sin garras de orden par tienen coincidencias perfectas , el descubrimiento de algoritmos de tiempo polinomial para encontrar el máximo conjuntos independientes en gráficos sin garras y la caracterización de gráficos perfectos sin garras . [1] Son el tema de cientos de trabajos de investigación matemática y varias encuestas. [1]
Ejemplos de
- El gráfico lineal L ( G ) de cualquier gráfico G está libre de garras; L ( G ) tiene un vértice para cada borde de G , y vértices son adyacentes en L ( G ) siempre que los bordes correspondientes comparten un punto final en G . Un gráfico de línea L ( G ) no puede contener una garra, porque si tres bordes ae 1 , e 2 , y e 3 en G todos los puntos finales compartir con otro borde e 4 a continuación, por el principio del palomar al menos dos de e 1 , e 2 , y e 3 deben compartir uno de esos puntos finales entre sí. Los gráficos de líneas se pueden caracterizar en términos de nueve subgrafos prohibidos; [2] la garra es el más simple de estos nueve gráficos. Esta caracterización proporcionó la motivación inicial para estudiar gráficos sin garras. [1]
- Los gráficos de De Bruijn (gráficos cuyos vértices representan cadenas binarias de n bits para algunos n , y cuyos bordes representan superposiciones de ( n - 1) bits entre dos cadenas) están libres de garras. Una forma de mostrar esto es mediante la construcción del gráfico de De Bruijn para cadenas de n bits como el gráfico lineal del gráfico de Bruijn para cadenas de ( n - 1) bits.
- El complemento de cualquier gráfico sin triángulos no tiene garras. [3] Estos gráficos incluyen como caso especial cualquier gráfico completo .
- Las gráficas de intervalo adecuadas , las gráficas de intervalo formadas como gráficas de intersección de familias de intervalos en las que ningún intervalo contiene otro intervalo, están libres de garras, porque cuatro intervalos que se intersecan correctamente no pueden cruzarse en el patrón de una garra. [3] Lo mismo es cierto de manera más general para las gráficas de arco circular adecuadas . [4]
- El eje de Moser , un gráfico de siete vértices utilizado para proporcionar un límite inferior para el número cromático del plano , no tiene garras.
- Los gráficos de varios poliedros y politopos están libres de garras, incluido el gráfico del tetraedro y, más en general, de cualquier simplex (un gráfico completo), el gráfico del octaedro y, más en general, de cualquier politopo cruzado ( isomorfo al gráfico de cóctel formado quitando una coincidencia perfecta de un gráfico completo), el gráfico del icosaedro regular , [5] y el gráfico de 16 celdas .
- El gráfico de Schläfli , un gráfico fuertemente regular con 27 vértices, no tiene garras. [5]
Reconocimiento
Es sencillo verificar que un gráfico dado con n vértices y m bordes no tiene garras en el tiempo O ( n 4 ), probando cada 4 tupla de vértices para determinar si inducen una garra. [6] Con más eficiencia y mayor complicación, se puede probar si un gráfico está libre de garras comprobando, para cada vértice del gráfico, que el gráfico del complemento de sus vecinos no contiene un triángulo. Una gráfica contiene un triángulo si y solo si el cubo de su matriz de adyacencia contiene un elemento diagonal distinto de cero, por lo que la búsqueda de un triángulo se puede realizar en el mismo límite de tiempo asintótico que la multiplicación de matrices n × n . [7] Por lo tanto, utilizando el algoritmo Coppersmith-Winograd , el tiempo total para este algoritmo de reconocimiento sin garras sería O ( n 3.376 ).
Kloks, Kratsch y Müller (2000) observan que en cualquier gráfico sin garras, cada vértice tiene como máximo 2 √ m vecinos; porque de lo contrario, según el teorema de Turán, los vecinos del vértice no tendrían suficientes aristas restantes para formar el complemento de un gráfico sin triángulos. Esta observación permite que la verificación de cada vecindario en el algoritmo basado en la multiplicación de matrices rápida descrito anteriormente se realice en el mismo tiempo asintótico limitado que la multiplicación de matrices de 2 √ m × 2 √ m , o más rápido para los vértices con grados aún más bajos. El peor caso para este algoritmo ocurre cuando los vértices Ω ( √ m ) tienen Ω ( √ m ) vecinos cada uno, y los vértices restantes tienen pocos vecinos, por lo que su tiempo total es O ( m 3.376 / 2 ) = O ( m 1.688 ).
Enumeración
Debido a que los gráficos sin garras incluyen complementos de gráficos sin triángulos, el número de gráficos sin garras en n vértices crece al menos tan rápido como el número de gráficos sin triángulos, exponencialmente en el cuadrado de n . Los números de gráficos sin garras conectados en n nodos, para n = 1, 2, ... son
- 1, 1, 2, 5, 14, 50, 191, 881, 4494, 26389, 184749, ... (secuencia A022562 en la OEIS ).
Si se permite desconectar los gráficos, el número de gráficos es aún mayor: son
- 1, 2, 4, 10, 26, 85, 302, 1285, 6170, ... (secuencia A086991 en la OEIS ).
Una técnica de Palmer, Read y Robinson (2002) permite contar el número de gráficos cúbicos sin garras de manera muy eficiente, inusualmente para problemas de enumeración de gráficos .
Emparejamientos
Sumner (1974) e, independientemente, Las Vergnas (1975) demostraron que todo grafo conectado sin garras con un número par de vértices tiene una correspondencia perfecta . [8] Es decir, existe un conjunto de aristas en el gráfico de modo que cada vértice es un punto final de exactamente una de las aristas coincidentes. El caso especial de este resultado para gráficos de líneas implica que, en cualquier gráfico con un número par de aristas, se pueden dividir las aristas en trayectorias de longitud dos. Los emparejamientos perfectos se pueden utilizar para proporcionar otra caracterización de los gráficos sin garras: son exactamente los gráficos en los que cada subgrafo inducido conectado de orden par tiene un emparejamiento perfecto. [8]
La prueba de Sumner muestra, con más fuerza, que en cualquier grafo sin garras conectado uno puede encontrar un par de vértices adyacentes cuya eliminación deja conectado el grafo restante. Para mostrar esto, Sumner encuentra un par de vértices u y v que son tan lejos como sea posible en el gráfico, y elige w a ser un vecino de v que está tan lejos de u como sea posible; como muestra, ni v ni w pueden encontrarse en ningún camino más corto desde cualquier otro nodo hacia u , por lo que la eliminación de v y w deja el gráfico restante conectado. La eliminación repetida de pares de vértices coincidentes de esta manera forma una coincidencia perfecta en el gráfico sin garras dado.
La misma idea de prueba se aplica de manera más general si u es cualquier vértice, v es cualquier vértice que esté máximamente lejos de u , y w es cualquier vecino de v que esté máximamente lejos de u . Además, la eliminación de v y w del gráfico no cambia ninguna de las otras distancias de u . Por lo tanto, el proceso de formar una coincidencia mediante la búsqueda y eliminación de pares vw que están máximamente lejos de u se puede realizar mediante un recorrido postorder único de un primer árbol de búsqueda de amplitud del gráfico, enraizado en u , en tiempo lineal. Chrobak, Naor y Novick (1989) proporcionan un algoritmo alternativo de tiempo lineal basado en la búsqueda en profundidad , así como algoritmos paralelos eficientes para el mismo problema.
Faudree, Flandrin & Ryjáček (1997) enumeran varios resultados relacionados, incluyendo los siguientes: ( r - 1) -conectado K 1, r -graficos libres de orden par tienen coincidencias perfectas para cualquier r ≥ 2; Los gráficos sin garras de orden impar con un vértice de un grado-uno como máximo pueden dividirse en un ciclo impar y una coincidencia; para cualquier k que sea como máximo la mitad del grado mínimo de un gráfico sin garras en el que k o el número de vértices es par, el gráfico tiene un factor k ; y, si un gráfico sin garras está conectado (2 k + 1), entonces cualquier coincidencia de bordes k puede extenderse a una coincidencia perfecta.
Conjuntos independientes
Un conjunto independiente en un gráfico de líneas corresponde a una coincidencia en su gráfico subyacente, un conjunto de bordes de los cuales no dos comparten un punto final. El algoritmo de flor de Edmonds (1965) encuentra una coincidencia máxima en cualquier gráfico en tiempo polinomial, lo que equivale a calcular un conjunto máximo independiente en gráficos lineales. Esto se ha extendido de forma independiente a un algoritmo para todos los gráficos sin garras por Sbihi (1980) y Minty (1980) . [9]
Ambos enfoques utilizan la observación de que en los gráficos sin garras, ningún vértice puede tener más de dos vecinos en un conjunto independiente, por lo que la diferencia simétrica de dos conjuntos independientes debe inducir un subgrafo de grado como máximo dos; es decir, es una unión de caminos y ciclos. En particular, si I es un conjunto independiente no máximo, se diferencia de cualquier conjunto independiente máximo por ciclos pares y los llamados caminos de aumento : caminos inducidos que alternan entre vértices que no están en I y vértices en I , y para los cuales ambos extremos solo tienen un vecino en I . Como la diferencia simétrica de I con cualquier camino de aumento da un conjunto independiente más grande, la tarea se reduce a buscar caminos de aumento hasta que no se puedan encontrar más, de manera análoga a como en los algoritmos para encontrar coincidencias máximas.
El algoritmo de Sbihi recrea el paso de contracción de la flor del algoritmo de Edmonds y agrega un paso de contracción de camarilla similar, pero más complicado . El enfoque de Minty es transformar la instancia del problema en un gráfico de línea auxiliar y usar el algoritmo de Edmonds directamente para encontrar las rutas de aumento. Después de una corrección de Nakamura & Tamura 2001 , el resultado de Minty también puede usarse para resolver en tiempo polinomial el problema más general de encontrar en gráficos sin garras un conjunto independiente de peso máximo. También se conocen generalizaciones de estos resultados a clases más amplias de gráficos. [9] Al mostrar un teorema de estructura novedoso , Faenza, Oriolo & Stauffer (2011) dieron un algoritmo de tiempo cúbico, que también funciona en la configuración ponderada.
Coloración, camarillas y dominación
Un gráfico perfecto es un gráfico en el que el número cromático y el tamaño de la camarilla máxima son iguales, y en el que esta igualdad persiste en cada subgrafo inducido. Ahora se sabe (el teorema de la gráfica perfecta fuerte ) que las gráficas perfectas pueden caracterizarse como las gráficas que no tienen como subgrafias inducidas ni un ciclo impar ni el complemento de un ciclo impar (el llamado agujero impar ). [10] Sin embargo, durante muchos años esto siguió siendo una conjetura sin resolver, sólo probada para subclases especiales de gráficos. Una de estas subclases fue la familia de gráficos sin garras: varios autores descubrieron que los gráficos sin garras sin ciclos impares y agujeros impares son perfectos. Los gráficos perfectos sin garras se pueden reconocer en tiempo polinomial. En un gráfico perfecto sin garras, la vecindad de cualquier vértice forma el complemento de un gráfico bipartito . Es posible colorear gráficos perfectos sin garras, o encontrar el máximo de camarillas en ellos, en tiempo polinomial. [11]
¿Los gráficos sin garras siempre tienen un número cromático de lista igual a su número cromático?
En general, es NP-difícil encontrar la camarilla más grande en un gráfico sin garras. [12] También es NP-difícil encontrar una coloración óptima de la gráfica, porque (a través de gráficos lineales) este problema generaliza el problema NP-difícil de calcular el índice cromático de una gráfica. [6] Por la misma razón, es NP-difícil encontrar una coloración que logre una proporción de aproximación mejor que 4/3. Sin embargo, se puede lograr una relación de aproximación de dos mediante un algoritmo de coloración codicioso , porque el número cromático de un gráfico sin garras es mayor que la mitad de su grado máximo. Una generalización de la conjetura de coloración de la lista de bordes establece que, para gráficos sin garras, el número cromático de la lista es igual al número cromático; estos dos números pueden estar muy separados en otros tipos de gráficos. [13]
Los gráficos sin garras están delimitados por χ , lo que significa que cada gráfico sin garras de gran número cromático contiene una gran camarilla. Más enérgicamente, del teorema de Ramsey se desprende que cada grafo sin garras de grado máximo grande contiene una camarilla grande, de tamaño aproximadamente proporcional a la raíz cuadrada del grado. Para gráficos sin garras conectados que incluyen al menos un conjunto independiente de tres vértices, es posible una relación más fuerte entre el número cromático y el tamaño de la camarilla: en estos gráficos, existe una camarilla de tamaño al menos la mitad del número cromático. [14]
Aunque no todos los gráficos sin garras son perfectos, los gráficos sin garras satisfacen otra propiedad, relacionada con la perfección. Una gráfica se llama dominación perfecta si tiene un conjunto dominante mínimo que es independiente y si la misma propiedad se mantiene en todos sus subgrafos inducidos. Los gráficos sin garras tienen esta propiedad. Para ver esto, sea D un conjunto dominante en un gráfico sin garras, y suponga que v y w son dos vértices adyacentes en D ; entonces el conjunto de vértices dominados por v pero no por w debe ser una camarilla (de lo contrario, v sería el centro de una garra). Si cada vértice de esta camarilla ya está dominado por al menos otro miembro de D , entonces v puede eliminarse produciendo un conjunto dominante independiente más pequeño, y de lo contrario v puede ser reemplazado por uno de los vértices no dominados en su camarilla produciendo un conjunto dominante con menos adyacencias. Al repetir este proceso de reemplazo, uno finalmente alcanza un conjunto dominante no mayor que D , por lo que, en particular, cuando el conjunto inicial D es un conjunto dominante mínimo, este proceso forma un conjunto dominante independiente igualmente pequeño. [15]
A pesar de esta propiedad de perfeccionamiento de dominación, es NP-difícil determinar el tamaño del conjunto dominante mínimo en un gráfico sin garras. [6] Sin embargo, en contraste con la situación para clases más generales de gráficos, encontrar el conjunto dominante mínimo o el conjunto dominante mínimo conectado en un gráfico sin garras es manejable con parámetros fijos : se puede resolver en el tiempo acotado por un polinomio en el tamaño del gráfico multiplicado por una función exponencial del tamaño del conjunto dominante. [dieciséis]
Estructura
Chudnovsky y Seymour (2005) resumen una serie de artículos en los que prueban una teoría de la estructura para gráficos sin garras, análoga al teorema de estructura de grafos para familias de grafos cerrados menores probado por Robertson y Seymour, y a la teoría de la estructura para grafos perfectos que Chudnovsky, Seymour y sus coautores utilizaron para demostrar el teorema del grafo perfecto fuerte. [10] La teoría es demasiado compleja para describirla en detalle aquí, pero para darle una idea, basta con esbozar dos de sus resultados. Primero, para una subclase especial de gráficos sin garras que ellos llaman gráficos cuasi-lineales (de manera equivalente, gráficos co-bipartitos localmente), establecen que cada gráfico tiene una de dos formas:
- Un gráfico de intervalo circular difuso , una clase de gráficos representados geométricamente por puntos y arcos en un círculo, generalizando gráficos de arco circular adecuados.
- Un gráfico construido a partir de un multigraph reemplazando cada borde por un gráfico de intervalo lineal difuso . Esto generaliza la construcción de un gráfico lineal, en el que cada borde del multigrafo se reemplaza por un vértice. Los gráficos de intervalo lineal difuso se construyen de la misma manera que los gráficos de intervalo circular difuso, pero en una línea en lugar de en un círculo.
Chudnovsky y Seymour clasifican gráficos sin garras conectados arbitrarios en uno de los siguientes:
- Seis subclases específicas de gráficos sin garras. Tres de estos son gráficos de líneas, gráficos de arco circular adecuados y los subgráficos inducidos de un icosaedro; los otros tres implican definiciones adicionales.
- Gráficos formados de cuatro formas simples a partir de gráficos más pequeños sin garras.
- Gráficos antipismáticos , una clase de gráficos densos definidos como los gráficos sin garras en los que cada cuatro vértices inducen un subgráfico con al menos dos aristas.
Gran parte del trabajo en su teoría de la estructura implica un análisis más detallado de los gráficos antipismáticos. El gráfico de Schläfli , un gráfico fuertemente regular sin garras con parámetros srg (27,16,10,8), juega un papel importante en esta parte del análisis. Esta teoría de la estructura ha dado lugar a nuevos avances en combinatoria poliédrica y nuevos límites en el número cromático de gráficos sin garras, [5] [17] así como a nuevos algoritmos de parámetros fijos manejables para dominar conjuntos en gráficos sin garras. [18]
Notas
- ↑ a b c Faudree, Flandrin y Ryjáček (1997) , p. 88.
- ^ Beineke (1968) .
- ↑ a b Faudree, Flandrin & Ryjáček (1997) , p. 89.
- ^ Chudnovsky y Seymour (2008) .
- ↑ a b c Chudnovsky y Seymour (2005) .
- ↑ a b c Faudree, Flandrin y Ryjáček (1997) , p. 132.
- ^ Itai y Rodeh (1978) .
- ↑ a b Faudree, Flandrin & Ryjáček (1997) , págs. 120-124.
- ↑ a b Faudree, Flandrin & Ryjáček (1997) , págs. 133-134.
- ^ a b Chudnovsky y col. (2006) .
- ^ Faudree, Flandrin y Ryjáček (1997) , págs. 135-136.
- ^ Faudree, Flandrin y Ryjáček (1997) observan en la p. 132 que la dureza NP de las camarillas en gráficos sin garras se deriva de la dureza NP del problema de conjuntos independientes en gráficos sin triángulos , probado NP-hard por Poljak (1974)
- ^ Gravier y Maffray (2004) .
- ^ Chudnovsky y Seymour (2010) .
- ^ Faudree, Flandrin y Ryjáček (1997) , págs. 124-125.
- ^ Cygan y col. (2011) ; Hermelin y col. (2011) .
- ^ King y Reed (2015) .
- ^ Hermelin y col. (2011) .
Referencias
- Beineke, LW (1968), "Gráficos derivados de dígrafos", en Sachs, H .; Voss, H.-J .; Walter, H.-J. (eds.), Beiträge zur Graphentheorie , Leipzig: Teubner, págs. 17–33.
- Chrobak, Marek; Naor, José; Novick, Mark B. (1989), "Uso de árboles de expansión de grados acotados en el diseño de algoritmos eficientes en gráficos sin garras", en Dehne, F .; Sack, J.-R. ; Santoro, N. (eds.), Algoritmos y estructuras de datos: Workshop WADS '89, Ottawa, Canadá, agosto de 1989, Proceedings , Lecture Notes in Comput. Sci., 382 , Berlín: Springer, págs. 147-162, doi : 10.1007 / 3-540-51542-9_13 , hdl : 1813/6891.
- Chudnovsky, Maria ; Robertson, Neil ; Seymour, Paul ; Thomas, Robin (2006), "El teorema del gráfico fuerte perfecto" (PDF) , Annals of Mathematics , 164 (1): 51-229, arXiv : math / 0212070 , doi : 10.4007 / annals.2006.164.51.
- Chudnovsky, Maria ; Seymour, Paul (2005), "La estructura de los gráficos sin garras" (PDF) , Encuestas en combinatoria 2005 , London Math. Soc. Lecture Note Ser., 327 , Cambridge: Cambridge Univ. Press, págs. 153-171, MR 2187738.
- Chudnovsky, Maria ; Seymour, Paul (2008), "Gráficos sin garras. III. Gráficos de intervalo circular" (PDF) , Journal of Combinatorial Theory , Serie B, 98 (4): 812–834, doi : 10.1016 / j.jctb.2008.03. 001 , MR 2418774.
- Chudnovsky, Maria ; Seymour, Paul (2010), "Claw-free graphs VI. Coloring", Journal of Combinatorial Theory , Serie B, 100 (6): 560–572, doi : 10.1016 / j.jctb.2010.04.005 , MR 2718677.
- Cygan, Marek; Philip, Geevarghese; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry (2011), "El conjunto dominante es un parámetro fijo que se puede tratar en gráficos sin garras", Informática teórica , 412 (50): 6982–7000, arXiv : 1011.6239 , doi : 10.1016 / j.tcs.2011.09.010 , MR 2894366.
- Edmonds, Jack (1965), "Senderos, árboles y flores", Canadian Journal of Mathematics , 17 (0): 449–467, doi : 10.4153 / CJM-1965-045-4 , MR 0177907.
- Faenza, Yuri; Oriolo, Gianpaolo; Stauffer, Gautier (2011), "Una descomposición algorítmica de gráficos sin garras que conduce a un algoritmo O (n 3 ) para el problema de conjuntos estables ponderados", Actas del vigésimo segundo simposio anual ACM-SIAM sobre algoritmos discretos (PDF ) , SODA '11, San Francisco, California: SIAM, págs. 630–646, doi : 10.1137 / 1.9781611973082.49.
- Faudree, Ralph ; Flandrin, Evelyne; Ryjáček, Zdeněk (1997), "Gráficos sin garras - Una encuesta", Matemáticas discretas , 164 (1–3): 87–147, doi : 10.1016 / S0012-365X (96) 00045-3 , MR 1432221.
- Goldberg, Andrew V .; Karzanov, Alexander V. (1996), "Problemas de trayectoria en gráficas simétricas sesgadas", Combinatorica , 16 (3): 353–382, doi : 10.1007 / BF01261321.
- Gravier, Sylvain; Maffray, Frédéric (2004), "On the choice number of claw-free perfect graphs", Discrete Mathematics , 276 (1-3): 211-218, doi : 10.1016 / S0012-365X (03) 00292-9 , MR 2046636.
- Hermelin, Danny; Mnich, Matthias; van Leeuwen, Erik Jan; Woeginger, Gerhard (2011), "Domination when the stars are out", Automata, Languages and Programming: 38th International Colloquium, ICALP 2011, Zurich, Suiza, 4-8 de julio de 2011, Proceedings, Part I , Lecture Notes in Computer Science , 6755 , Zúrich, Suiza, págs. 462–473, arXiv : 1012.0012 , doi : 10.1007 / 978-3-642-22006-7_39.
- Itai, Alon; Rodeh, Michael (1978), "Encontrar un circuito mínimo en un gráfico", SIAM Journal on Computing , 7 (4): 413–423, doi : 10.1137 / 0207033 , MR 0508603.
- King, Andrew D .; Reed, Bruce A. (2015), "Gráficos sin garras, gráficos esqueléticos y una conjetura más fuerte sobre ω, Δ y χ", Journal of Graph Theory , 78 (3): 157-194, arXiv : 1212.3036 , doi : 10.1002 / jgt.21797.
- Kloks, Ton; Kratsch, Dieter; Müller, Haiko (2000), "Encontrar y contar pequeños subgrafos inducidos de manera eficiente", Information Processing Letters , 74 (3–4): 115–121, doi : 10.1016 / S0020-0190 (00) 00047-8 , MR 1761552.
- Las Vergnas, M. (1975), "A note on matchings in graphs", Cahiers du Centre d'Études de Recherche Opérationnelle , 17 (2-3-4): 257-260, MR 0412042.
- Minty, George J. (1980), "Sobre conjuntos máximos independientes de vértices en gráficos sin garras", Journal of Combinatorial Theory, Serie B , 28 (3): 284-304, doi : 10.1016 / 0095-8956 (80) 90074-X , MR 0579076.
- Nakamura, Daishin; Tamura, Akihisa (2001), "Una revisión del algoritmo de Minty para encontrar un conjunto estable ponderado máximo de un gráfico sin garras" , Revista de la Sociedad de Investigación de Operaciones de Japón , 44 (2): 194-204.
- Palmer, Edgar M .; Leer, Ronald C .; Robinson, Robert W. (2002), "Contando gráficas cúbicas sin garras" (PDF) , SIAM Journal on Discrete Mathematics , 16 (1): 65–73, doi : 10.1137 / S0895480194274777 , MR 1972075.
- Poljak, Svatopluk (1974), "Una nota sobre conjuntos estables y coloraciones de gráficos", Commentationes Mathematicae Universitatis Carolinae , 15 : 307-309, MR 0351881.
- Sbihi, Najiba (1980), "Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoile", Discrete Mathematics , 29 (1): 53–76, doi : 10.1016 / 0012-365X (90) 90287-R , MR 0553650.
- Sumner, David P. (1974), "Gráficos con 1 factores", Actas de la American Mathematical Society , American Mathematical Society, 42 (1): 8-12, doi : 10.2307 / 2039666 , JSTOR 2039666 , MR 0323648.
enlaces externos
- Gráficos sin garras , sistema de información sobre inclusiones de clases de gráficos
- Mugan, Jonathan William; Weisstein, Eric W. , "Gráfico sin garras" , MathWorld