Grafo bien cubierto

En teoría de grafos, un grafo bien cubierto (en inglés, well-covered graph) es un grafo no dirigido en el que todas las coberturas de vértices minimales tienen el mismo tamaño. Aquí, una cobertura de vértices es un conjunto de vértices que toca todas las aristas, y es minimal si al quitarle cualquier vértice alguna arista queda sin cubrir. De forma equivalente, los grafos bien cubiertos son aquellos en los que todos los conjuntos independientes maximales tienen el mismo tamaño. Michael D. Plummer definió y estudió por primera vez los grafos bien cubiertos en 1970.

Entre los grafos bien cubiertos se encuentran todos los grafos completos, los grafos bipartitos completos equilibrados y los grafos de la torre, cuyos vértices representan las casillas de un tablero de ajedrez y cuyas aristas representan los movimientos de una torre. Las caracterizaciones conocidas de los grafos cúbicos bien cubiertos, de los grafos sin garras bien cubiertos y de los grafos bien cubiertos de cintura grande permiten reconocer estos grafos en tiempo polinómico, pero comprobar si otros tipos de grafos son bien cubiertos es un problema co-NP-completo.

Definiciones

Una cobertura de vértices de un grafo no dirigido es un conjunto de vértices que toca todas las aristas del grafo. Una cobertura de vértices es minimal, o irredundante, si al quitarle cualquier vértice se pierde la propiedad de cobertura, es decir, alguna arista queda sin cubrir. Es mínima si no existe otra cobertura de vértices con menos vértices. Un grafo bien cubierto es aquel en el que toda cobertura minimal es también mínima. En el artículo original en el que definió los grafos bien cubiertos, Plummer señala que esto equivale a que dos coberturas minimales cualesquiera tengan el mismo número de vértices.

Un conjunto independiente de un grafo es un conjunto de vértices en el que no hay dos adyacentes entre sí. Si $C$ es una cobertura de vértices de un grafo $G$ , el complemento de $C$ es necesariamente un conjunto independiente, y viceversa. $C$ es una cobertura de vértices minimal si y solo si su complemento $I$ es un conjunto independiente maximal, y $C$ es una cobertura de vértices mínima si y solo si su complemento es un conjunto independiente máximo. Por tanto, un grafo bien cubierto es, de forma equivalente, un grafo en el que todos los conjuntos independientes maximales tienen el mismo tamaño, o un grafo en el que todo conjunto independiente maximal es máximo.

En el artículo original en el que se definieron los grafos bien cubiertos, estas definiciones se restringían a los grafos conexos, aunque también tienen sentido para grafos no conexos. Algunos autores posteriores sustituyeron el requisito de conexidad por el requisito, más débil, de que un grafo bien cubierto no tenga vértices aislados. Tanto en los grafos bien cubiertos conexos como en los grafos bien cubiertos sin vértices aislados no puede haber vértices esenciales, es decir, vértices que pertenezcan a todas las coberturas de vértices mínimas. Además, todo grafo bien cubierto es un grafo crítico para la cobertura de vértices, en el sentido de que, para cada vértice $v$ , al eliminar $v$ del grafo se obtiene un grafo con una cobertura de vértices mínima más pequeña.

El complejo de independencia de un grafo $G$ es el complejo simplicial que tiene un símplice por cada conjunto independiente de $G$ . Se dice que un complejo simplicial es puro si todos sus símplices maximales tienen el mismo cardinal, de modo que un grafo bien cubierto es, de forma equivalente, un grafo con un complejo de independencia puro.

Ejemplos

Ocho torres colocadas en un tablero de ajedrez sin que ninguna ataque a otra. Si se colocan menos de ocho torres sin que se ataquen entre sí, siempre se pueden completar hasta ocho torres que sigan sin atacarse.

Un grafo ciclo de longitud cuatro o cinco es bien cubierto: en ambos casos, todos los conjuntos independientes maximales tienen tamaño dos. Un ciclo de longitud siete y un camino de longitud tres también son bien cubiertos. Todo grafo completo es bien cubierto: cada conjunto independiente maximal consta de un solo vértice. Del mismo modo, todo grafo de clústeres (una unión disjunta de grafos completos) es bien cubierto. Un grafo bipartito completo es bien cubierto si los dos lados de su bipartición tienen el mismo número de vértices, ya que estos son sus dos únicos conjuntos independientes maximales. El grafo complemento de un grafo bipartito sin vértices aislados es bien cubierto: no tiene conjuntos independientes de más de dos vértices, y cada vértice puede ampliarse a un conjunto independiente de dos vértices.

Un grafo de la torre es bien cubierto: si se coloca cualquier conjunto de torres en un tablero de ajedrez de modo que no haya dos torres que se ataquen, siempre es posible seguir colocando más torres que no se ataquen hasta que haya una en cada fila y en cada columna del tablero. El grafo cuyos vértices son las diagonales de un polígono simple y cuyas aristas unen los pares de diagonales que se cruzan es bien cubierto, porque sus conjuntos independientes maximales son las triangulaciones del polígono y todas las triangulaciones tienen el mismo número de aristas.

Si $G$ es un grafo cualquiera de $n$ vértices, el producto enraizado de $G$ con un grafo de una sola arista (es decir, el grafo $H$ que se obtiene añadiendo a $G$ $n$ vértices nuevos, cada uno de grado uno y adyacente a un vértice distinto de $G$ ) es bien cubierto. En efecto, un conjunto independiente maximal de $H$ debe estar formado por un conjunto independiente arbitrario de $G$ junto con los vecinos de grado uno del conjunto complementario, y por tanto debe tener tamaño $n$ . De forma más general, dado un grafo cualquiera $G$ junto con un cubrimiento por cliques (una partición $p$ de los vértices de $G$ en cliques), el grafo $G p$ que se obtiene añadiendo un vértice más a cada clique es bien cubierto; el producto enraizado es el caso particular de esta construcción en el que $p$ consta de $n$ cliques de un solo vértice. Así, todo grafo es un subgrafo inducido de un grafo bien cubierto.

Bipartición, grafos muy bien cubiertos y cintura

Favaron (1982) define un grafo muy bien cubierto como un grafo bien cubierto (posiblemente no conexo, pero sin vértices aislados) en el que cada conjunto independiente maximal (y, por tanto, también cada cobertura de vértices minimal) contiene exactamente la mitad de los vértices. Esta definición incluye los productos enraizados de un grafo $G$ y un grafo de una sola arista. Incluye también, por ejemplo, los grafos bipartitos bien cubiertos estudiados por Ravindra (1977): en un grafo bipartito sin vértices aislados, los dos lados de cualquier bipartición forman conjuntos independientes maximales (y coberturas de vértices minimales), así que, si el grafo es bien cubierto, ambos lados deben tener el mismo número de vértices. En un grafo bien cubierto con $n$ vértices y sin vértices aislados, el tamaño de un conjunto independiente máximo es como mucho $n /2$ , de modo que los grafos muy bien cubiertos son los grafos bien cubiertos en los que el tamaño del conjunto independiente máximo es el mayor posible.

Un grafo bipartito conexo $G$ sin vértices aislados es bien cubierto si y solo si tiene un emparejamiento perfecto $M$ con la propiedad de que, para cada arista $uv$ de $M$ , el subgrafo inducido por los vecinos de $u$ y $v$ es un grafo bipartito completo. La caracterización mediante emparejamientos puede extenderse de los grafos bipartitos a los grafos muy bien cubiertos: un grafo $G$ es muy bien cubierto si y solo si tiene un emparejamiento perfecto $M$ con las dos propiedades siguientes:

ninguna arista de $M$ pertenece a un triángulo de $G$ , y
si una arista de $M$ es la arista central de un camino de tres aristas de $G$ , entonces los dos extremos del camino deben ser adyacentes.

Además, si $G$ es muy bien cubierto, todo emparejamiento perfecto de $G$ cumple estas propiedades.

Los árboles son un caso particular de grafo bipartito, y comprobar si un árbol es bien cubierto puede tratarse como un caso particular, mucho más sencillo, de la caracterización de los grafos bipartitos bien cubiertos: si $G$ es un árbol con más de dos vértices, es bien cubierto si y solo si cada nodo que no es hoja es adyacente exactamente a una hoja. La misma caracterización se aplica a los grafos que localmente se parecen a un árbol, en el sentido de que los entornos de diámetro pequeño de cada vértice son acíclicos: si un grafo tiene cintura ocho o más (de modo que, para cada vértice $v$ , el subgrafo de los vértices a distancia como mucho tres de $v$ es acíclico), entonces es bien cubierto si y solo si cada vértice de grado mayor que uno tiene exactamente un vecino de grado uno. A los grafos bien cubiertos de cintura cinco o más se les aplica una caracterización estrechamente relacionada, pero más compleja.

Regularidad y planaridad

Los grafos cúbicos (3-regulares) bien cubiertos están clasificados: son siete ejemplos 3-conexos, junto con tres familias infinitas de grafos cúbicos de menor conectividad.

Los siete grafos cúbicos 3-conexos bien cubiertos son el grafo completo $K 4$ , los grafos del prisma triangular y del prisma pentagonal, el grafo de Durero, el grafo de servicios $K 3,3$ , un grafo de ocho vértices que se obtiene del grafo de servicios mediante una transformación Y-Δ y el grafo de Petersen generalizado de 14 vértices $G (7,2)$ . De ellos, los cuatro primeros son grafos planos. Son los cuatro únicos grafos poliédricos cúbicos (grafos de poliedros convexos simples) que son bien cubiertos. Cuatro de estos grafos (los dos prismas, el grafo de Durero y $G (7,2)$ ) son grafos de Petersen generalizados.

Los grafos cúbicos bien cubiertos 1-conexos y 2-conexos se forman todos sustituyendo los nodos de un camino o de un ciclo por tres fragmentos de grafo que Plummer (1993) denomina $A$ , $B$ y $C$ . Los fragmentos $A$ o $B$ pueden sustituir a los nodos de un ciclo o a los nodos interiores de un camino, mientras que el fragmento $C$ se usa para sustituir los dos nodos extremos de un camino. El fragmento $A$ contiene un puente, por lo que el resultado de aplicar este proceso de sustitución a un camino, usando el fragmento $A$ para sustituir algunos de sus nodos (y los otros dos fragmentos para los nodos restantes), es un grafo cúbico bien cubierto 1-conexo por vértices. Todos los grafos cúbicos bien cubiertos 1-conexos por vértices tienen esta forma, y todos ellos son planos.

Hay dos tipos de grafos cúbicos bien cubiertos 2-conexos por vértices. Una de las dos familias se forma sustituyendo los nodos de un ciclo por fragmentos $A$ y $B$ , con al menos dos fragmentos del tipo $A$ ; un grafo de este tipo es plano si y solo si no contiene ningún fragmento del tipo $B$ . La otra familia se forma sustituyendo los nodos de un camino por fragmentos de los tipos $B$ y $C$ ; todos estos grafos son planos.

Como complemento de la caracterización de los poliedros simples bien cubiertos en tres dimensiones, también se han estudiado los poliedros simpliciales bien cubiertos o, de forma equivalente, los grafos planos maximales bien cubiertos. Todo grafo plano maximal con cinco o más vértices tiene conectividad por vértices 3, 4 o 5. No hay grafos planos maximales 5-conexos bien cubiertos, y solo hay cuatro grafos planos maximales 4-conexos bien cubiertos: los grafos del octaedro regular, de la bipirámide pentagonal, del biesfenoide romo y de un poliedro irregular (un deltaedro no convexo) con 12 vértices, 30 aristas y 20 caras triangulares. Sin embargo, hay infinitos grafos planos maximales 3-conexos bien cubiertos. Por ejemplo, si un grafo plano maximal de $3 t$ vértices tiene $t$ caras triangulares disjuntas, estas caras forman un cubrimiento por cliques. Por tanto, la construcción mediante cubrimientos por cliques, que en estos grafos consiste en subdividir cada uno de estos $t$ triángulos en tres triángulos nuevos que se encuentran en un vértice central, produce un grafo plano maximal bien cubierto.

Complejidad

Comprobar si un grafo contiene dos conjuntos independientes maximales de tamaños distintos es un problema NP-completo; es decir, de forma complementaria, comprobar si un grafo es bien cubierto es co-NP-completo. Aunque es fácil encontrar conjuntos independientes máximos en grafos de los que se sabe que son bien cubiertos, también es NP-difícil que un algoritmo produzca como salida, para cualquier grafo, o bien un conjunto independiente máximo o bien una garantía de que la entrada no es bien cubierta.

En cambio, es posible comprobar en tiempo polinómico si un grafo dado $G$ es muy bien cubierto. Para ello, se busca el subgrafo $H$ de $G$ formado por las aristas que cumplen las dos propiedades de una arista del emparejamiento en un grafo muy bien cubierto y, a continuación, se usa un algoritmo de emparejamiento para comprobar si $H$ tiene un emparejamiento perfecto. Algunos problemas que son NP-completos para grafos arbitrarios, como el de encontrar un ciclo hamiltoniano, también pueden resolverse en tiempo polinómico para los grafos muy bien cubiertos.

Se dice que un grafo es "equiemparejable" (en inglés, equimatchable) si todo emparejamiento maximal es máximo; es decir, es equiemparejable si su grafo línea es bien cubierto. En un sentido más fuerte, se dice que es "aleatoriamente emparejable" (randomly matchable) si todo emparejamiento maximal es un emparejamiento perfecto. Los únicos grafos conexos aleatoriamente emparejables son los grafos completos y los grafos bipartitos completos equilibrados. Es posible comprobar en tiempo polinómico si un grafo línea o, de forma más general, un grafo sin garras es bien cubierto.

Las caracterizaciones de los grafos bien cubiertos de cintura cinco o más y de los grafos bien cubiertos 3-regulares también dan lugar a algoritmos eficientes de tiempo polinómico para reconocer estos grafos.

Notas

1 2 Plummer, 1993, sección 1.
↑ Plummer (1970). Plummer emplea point («punto») para referirse a un vértice del grafo, line («línea») para una arista y point cover («cobertura de puntos») para una cobertura de vértices; esta terminología ha caído en desuso.
↑ Plummer, 1993.
1 2 3 Plummer, 1970.
↑ Favaron, 1982.
↑ Berge, 1981, p. 117.
↑ Berge, 1981, pp. 117-118.
↑ Para ejemplos de artículos que emplean esta terminología, véanse Dochtermann y Engström (2009) y Cook y Nagel (2012).
1 2 Sankaranarayana, 1994, sección 2.4, «Examples», p. 7.
↑ Los grafos de la torre son, de forma equivalente, los grafos línea de los grafos bipartitos completos, por lo que la propiedad de ser bien cubiertos de los grafos de la torre equivale al hecho de que los grafos bipartitos completos son equiemparejables; véanse Sumner (1979) y Lesk, Plummer y Pulleyblank (1984).
↑ Greenberg, 1993.
↑ Fink et al. (1985) estudiaron esta clase de ejemplos; son también (junto con el ciclo de cuatro aristas, que también es bien cubierto) exactamente los grafos cuyo número de dominación es $n /2$ . Su propiedad de ser bien cubiertos se enuncia también con otra terminología (tener un complejo de independencia puro) como teorema 4.4 de Dochtermann y Engström (2009), y aparece en Sankaranarayana (1994), cap. 3, «Dominating cycle and other problems».
↑ Para la construcción mediante cubrimientos por cliques, véase Cook y Nagel (2012), lema 3.2. Esta fuente enuncia sus resultados en términos de la pureza del complejo de independencia y emplea el término fully-whiskered para el caso particular del producto enraizado.
1 2 Plummer, 1993, sección 3.
↑ Ravindra (1977); Plummer (1993), teorema 3.1.
1 2 Staples (1975); Favaron (1982); Plummer (1993), teorema 3.3.
↑ Ravindra (1977); Plummer (1993), corolario 3.2.
↑ Finbow y Hartnell (1983); Plummer (1993), teorema 4.1.
↑ Finbow, Hartnell y Nowakowski (1993); Plummer (1993), teorema 4.2.
1 2 3 Campbell (1987); Campbell y Plummer (1988); Plummer (1993), teoremas 5.4 y 5.5.
↑ Campbell (1987); Finbow, Hartnell y Nowakowski (1988); Campbell, Ellingham y Royle (1993); Plummer (1993), teorema 5.7.
↑ Campbell y Plummer, 1988.
↑ Los grafos completos de 1, 2, 3 y 4 vértices son todos planos maximales y bien cubiertos; su conectividad por vértices es no acotada o como mucho tres, según detalles de la definición de conectividad por vértices que no son relevantes para grafos planos maximales mayores.
↑ Finbow et al. (2003); Finbow et al. (2009); Finbow et al. (2010).
↑ Finbow et al. (2016) denominan a los grafos construidos de este modo la familia $K_{4}$ ; se pueden construir más ejemplos mediante una operación que llaman O-join para combinar grafos más pequeños.
↑ Sankaranarayana y Stewart (1992); Chvátal y Slater (1993); Caro, Sebő y Tarsi (1996).
↑ Raghavan y Spinrad (2003).
↑ Sankaranarayana y Stewart (1992); Sankaranarayana (1994), cap. 3, tabla de resultados de complejidad.
↑ Lesk, Plummer y Pulleyblank, 1984.
↑ Sumner, 1979.
↑ Lesk, Plummer y Pulleyblank (1984); Tankus y Tarsi (1996); Tankus y Tarsi (1997).
↑ Campbell, Ellingham y Royle (1993); Plummer (1993), secciones 4 y 5.

Bibliografía

Berge, Claude (1981). «Some common properties for regularizable graphs, edge-critical graphs and B-graphs». Graph theory and algorithms (Proc. Sympos., Res. Inst. Electr. Comm., Tohoku Univ., Sendai, 1980) [Algunas propiedades comunes de los grafos regularizables, los grafos arista-críticos y los B-grafos]. Lecture Notes in Computer Science (en inglés) 108. Berlín: Springer. pp. 108-123. ISBN 978-3-540-10704-0. MR 622929. doi:10.1007/3-540-10704-5_10.
Campbell, S. R. (1987). Some results on planar well-covered graphs [Algunos resultados sobre grafos planos bien cubiertos] (Tesis doctoral) (en inglés). Vanderbilt University, Department of Mathematics. Citado por Plummer (1993).
Campbell, S. R.; Ellingham, M. N.; Royle, Gordon F. (1993). «A characterisation of well-covered cubic graphs» [Una caracterización de los grafos cúbicos bien cubiertos]. Journal of Combinatorial Mathematics and Combinatorial Computing (en inglés) 13: 193-212. MR 1220613.
Campbell, Stephen R.; Plummer, Michael D. (1988). «On well-covered 3-polytopes» [Sobre los 3-politopos bien cubiertos]. Ars Combinatoria (en inglés) 25 (A): 215-242. MR 942505.
Caro, Yair; Sebő, András; Tarsi, Michael (1996). «Recognizing greedy structures» [Reconocimiento de estructuras voraces]. Journal of Algorithms (en inglés) 20 (1): 137-156. MR 1368720. doi:10.1006/jagm.1996.0006.
Chvátal, Václav; Slater, Peter J. (1993). «A note on well-covered graphs». Quo vadis, graph theory? [Una nota sobre los grafos bien cubiertos]. Annals of Discrete Mathematics (en inglés) 55. Ámsterdam: North-Holland. pp. 179-181. MR 1217991.
Cook, David, II; Nagel, Uwe (2012). «Cohen-Macaulay graphs and face vectors of flag complexes» [Grafos de Cohen-Macaulay y vectores de caras de complejos bandera]. SIAM Journal on Discrete Mathematics (en inglés) 26 (1): 89-101. arXiv:1003.4447. doi:10.1137/100818170.
Dochtermann, Anton; Engström, Alexander (2009). «Algebraic properties of edge ideals via combinatorial topology» [Propiedades algebraicas de los ideales de aristas mediante topología combinatoria]. Electronic Journal of Combinatorics (en inglés) 16 (2): Research Paper 2. MR 2515765. arXiv:0810.4120. doi:10.37236/68.
Favaron, O. (1982). «Very well covered graphs» [Grafos muy bien cubiertos]. Discrete Mathematics (en inglés) 42 (2-3): 177-187. MR 677051. doi:10.1016/0012-365X(82)90215-1.
Finbow, A. S.; Hartnell, B. L. (1983). «A game related to covering by stars» [Un juego relacionado con el cubrimiento por estrellas]. Ars Combinatoria (en inglés) 16 (A): 189-198. MR 737090.
Finbow, A.; Hartnell, B.; Nowakowski, R. (1988). «Well-dominated graphs: a collection of well-covered ones» [Grafos bien dominados: una colección de grafos bien cubiertos]. Ars Combinatoria (en inglés) 25 (A): 5-10. MR 942485.
Finbow, A.; Hartnell, B.; Nowakowski, R. J. (1993). «A characterization of well covered graphs of girth 5 or greater» [Una caracterización de los grafos bien cubiertos de cintura 5 o mayor]. Journal of Combinatorial Theory, Series B (en inglés) 57 (1): 44-68. MR 1198396. doi:10.1006/jctb.1993.1005.
Finbow, A.; Hartnell, B.; Nowakowski, R.; Plummer, Michael D. (2003). «On well-covered triangulations. I» [Sobre las triangulaciones bien cubiertas. I]. Discrete Applied Mathematics (en inglés) 132 (1-3): 97-108. MR 2024267. doi:10.1016/S0166-218X(03)00393-7.
Finbow, Arthur S.; Hartnell, Bert L.; Nowakowski, Richard J.; Plummer, Michael D. (2009). «On well-covered triangulations. II» [Sobre las triangulaciones bien cubiertas. II]. Discrete Applied Mathematics (en inglés) 157 (13): 2799-2817. MR 2537505. doi:10.1016/j.dam.2009.03.014.
Finbow, Arthur S.; Hartnell, Bert L.; Nowakowski, Richard J.; Plummer, Michael D. (2010). «On well-covered triangulations. III» [Sobre las triangulaciones bien cubiertas. III]. Discrete Applied Mathematics (en inglés) 158 (8): 894-912. MR 2602814. doi:10.1016/j.dam.2009.08.002.
Finbow, Arthur S.; Hartnell, Bert L.; Nowakowski, Richard J.; Plummer, Michael D. (2016). «Well-covered triangulations: Part IV» [Triangulaciones bien cubiertas: parte IV]. Discrete Applied Mathematics (en inglés) 215: 71-94. MR 3548980. doi:10.1016/j.dam.2016.06.030.
Fink, J. F.; Jacobson, M. S.; Kinch, L. F.; Roberts, J. (1985). «On graphs having domination number half their order» [Sobre los grafos cuyo número de dominación es la mitad de su orden]. Periodica Mathematica Hungarica (en inglés) 16 (4): 287-293. MR 0833264. doi:10.1007/BF01848079.
Greenberg, Peter (1993). «Piecewise SL₂Z geometry» [Geometría SL₂Z a trozos]. Transactions of the American Mathematical Society (en inglés) 335 (2): 705-720. JSTOR 2154401. MR 1140914. doi:10.2307/2154401.
Lesk, M.; Plummer, M. D.; Pulleyblank, W. R. (1984). «Equi-matchable graphs». En Bollobás, Béla, ed. Graph Theory and Combinatorics: Proceedings of the Cambridge Combinatorial Conference, in Honour of Paul Erdős [Grafos equiemparejables] (en inglés). Londres: Academic Press. pp. 239-254. MR 777180.
Plummer, Michael D. (1970). «Some covering concepts in graphs» [Algunos conceptos de cobertura en grafos]. Journal of Combinatorial Theory (en inglés) 8 (1): 91-98. MR 0289347. doi:10.1016/S0021-9800(70)80011-4.
Plummer, Michael D. (1993). «Well-covered graphs: a survey» [Grafos bien cubiertos: una revisión]. Quaestiones Mathematicae (en inglés) 16 (3): 253-287. MR 1254158. doi:10.1080/16073606.1993.9631737. Archivado desde el original el 27 de mayo de 2012.
Raghavan, Vijay; Spinrad, Jeremy (2003). «Robust algorithms for restricted domains» [Algoritmos robustos para dominios restringidos]. Journal of Algorithms (en inglés) 48 (1): 160-172. MR 2006100. doi:10.1016/S0196-6774(03)00048-8.
Ravindra, G. (1977). «Well-covered graphs» [Grafos bien cubiertos]. Journal of Combinatorics, Information and System Sciences (en inglés) 2 (1): 20-21. MR 0469831.
Sankaranarayana, Ramesh S. (1994). Well-covered graphs: some new sub-classes and complexity results [Grafos bien cubiertos: algunas subclases nuevas y resultados de complejidad] (Tesis doctoral) (en inglés). University of Alberta.
Sankaranarayana, Ramesh S.; Stewart, Lorna K. (1992). «Complexity results for well-covered graphs» [Resultados de complejidad para grafos bien cubiertos]. Networks (en inglés) 22 (3): 247-262. MR 1161178. doi:10.1002/net.3230220304.
Staples, J. (1975). On some subclasses of well-covered graphs [Sobre algunas subclases de grafos bien cubiertos] (Tesis doctoral) (en inglés). Vanderbilt University, Department of Mathematics. Citado por Plummer (1993).
Sumner, David P. (1979). «Randomly matchable graphs» [Grafos aleatoriamente emparejables]. Journal of Graph Theory (en inglés) 3 (2): 183-186. MR 530304. doi:10.1002/jgt.3190030209.
Tankus, David; Tarsi, Michael (1996). «Well-covered claw-free graphs» [Grafos sin garras bien cubiertos]. Journal of Combinatorial Theory, Series B (en inglés) 66 (2): 293-302. MR 1376052. doi:10.1006/jctb.1996.0022.
Tankus, David; Tarsi, Michael (1997). «The structure of well-covered graphs and the complexity of their recognition problems» [La estructura de los grafos bien cubiertos y la complejidad de sus problemas de reconocimiento]. Journal of Combinatorial Theory, Series B (en inglés) 69 (2): 230-233. MR 1438624. doi:10.1006/jctb.1996.1742.

Datos: Q7981049

[FOOTNOTEPlummer1993sección_1-1] 1 2 Plummer, 1993, sección 1.

[2] Plummer (1970). Plummer emplea point («punto») para referirse a un vértice del grafo, line («línea») para una arista y point cover («cobertura de puntos») para una cobertura de vértices; esta terminología ha caído en desuso.

[FOOTNOTEPlummer1993-3] Plummer, 1993.

[FOOTNOTEPlummer1970-4] 1 2 3 Plummer, 1970.

[FOOTNOTEFavaron1982-5] Favaron, 1982.

[FOOTNOTEBerge1981117-6] Berge, 1981, p. 117.

[FOOTNOTEBerge1981117-118-7] Berge, 1981, pp. 117-118.

[8] Para ejemplos de artículos que emplean esta terminología, véanse Dochtermann y Engström (2009) y Cook y Nagel (2012).

[FOOTNOTESankaranarayana1994sección_2.4,_«Examples»,_p._7-9] 1 2 Sankaranarayana, 1994, sección 2.4, «Examples», p. 7.

[10] Los grafos de la torre son, de forma equivalente, los grafos línea de los grafos bipartitos completos, por lo que la propiedad de ser bien cubiertos de los grafos de la torre equivale al hecho de que los grafos bipartitos completos son equiemparejables; véanse Sumner (1979) y Lesk, Plummer y Pulleyblank (1984).

[FOOTNOTEGreenberg1993-11] Greenberg, 1993.

[12] Fink et al. (1985) estudiaron esta clase de ejemplos; son también (junto con el ciclo de cuatro aristas, que también es bien cubierto) exactamente los grafos cuyo número de dominación es $n /2$ . Su propiedad de ser bien cubiertos se enuncia también con otra terminología (tener un complejo de independencia puro) como teorema 4.4 de Dochtermann y Engström (2009), y aparece en Sankaranarayana (1994), cap. 3, «Dominating cycle and other problems».

[cn10-13] Para la construcción mediante cubrimientos por cliques, véase Cook y Nagel (2012), lema 3.2. Esta fuente enuncia sus resultados en términos de la pureza del complejo de independencia y emplea el término fully-whiskered para el caso particular del producto enraizado.

[FOOTNOTEPlummer1993sección_3-14] 1 2 Plummer, 1993, sección 3.

[r77p93-15] Ravindra (1977); Plummer (1993), teorema 3.1.

[sfp-16] 1 2 Staples (1975); Favaron (1982); Plummer (1993), teorema 3.3.

[17] Ravindra (1977); Plummer (1993), corolario 3.2.

[18] Finbow y Hartnell (1983); Plummer (1993), teorema 4.1.

[19] Finbow, Hartnell y Nowakowski (1993); Plummer (1993), teorema 4.2.

[ccpp-20] 1 2 3 Campbell (1987); Campbell y Plummer (1988); Plummer (1993), teoremas 5.4 y 5.5.

[21] Campbell (1987); Finbow, Hartnell y Nowakowski (1988); Campbell, Ellingham y Royle (1993); Plummer (1993), teorema 5.7.

[FOOTNOTECampbellPlummer1988-22] Campbell y Plummer, 1988.

[23] Los grafos completos de 1, 2, 3 y 4 vértices son todos planos maximales y bien cubiertos; su conectividad por vértices es no acotada o como mucho tres, según detalles de la definición de conectividad por vértices que no son relevantes para grafos planos maximales mayores.

[24] Finbow et al. (2003); Finbow et al. (2009); Finbow et al. (2010).

[25] Finbow et al. (2016) denominan a los grafos construidos de este modo la familia $K_{4}$ ; se pueden construir más ejemplos mediante una operación que llaman O-join para combinar grafos más pequeños.

[26] Sankaranarayana y Stewart (1992); Chvátal y Slater (1993); Caro, Sebő y Tarsi (1996).

[27] Raghavan y Spinrad (2003).

[28] Sankaranarayana y Stewart (1992); Sankaranarayana (1994), cap. 3, tabla de resultados de complejidad.

[FOOTNOTELeskPlummerPulleyblank1984-29] Lesk, Plummer y Pulleyblank, 1984.

[FOOTNOTESumner1979-30] Sumner, 1979.

[31] Lesk, Plummer y Pulleyblank (1984); Tankus y Tarsi (1996); Tankus y Tarsi (1997).

[32] Campbell, Ellingham y Royle (1993); Plummer (1993), secciones 4 y 5.