En teoría de grafos , un gráfico bien cubierto es un gráfico no dirigido en el que cada cobertura de vértice mínimo tiene el mismo tamaño que cualquier otra cobertura de vértice mínimo. De manera equivalente, estos son los gráficos en los que cada conjunto máximo independiente tiene el mismo tamaño. Plummer (1970) definió y estudió por primera vez gráficos bien cubiertos .
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/9/94/Well-covered_graph.svg/220px-Well-covered_graph.svg.png)
Los gráficos bien cubiertos incluyen todos los gráficos completos , gráficos bipartitos completos equilibrados y los gráficos de la torre cuyos vértices representan los cuadrados de un tablero de ajedrez y los bordes representan los movimientos de una torre de ajedrez. Las caracterizaciones conocidas de los gráficos cúbicos bien cubiertos , los gráficos sin garras bien cubiertos y los gráficos bien cubiertos de circunferencia alta permiten que estos gráficos se reconozcan en tiempo polinomial , pero probar si otros tipos de gráficos están bien cubiertos es un coNP -problema completo .
Definiciones
Una cobertura de vértice en un gráfico es un conjunto de vértices que toca todos los bordes del gráfico. Una cobertura de vértice es mínima, o irredundante, si eliminar cualquier vértice de ella destruiría la propiedad de cobertura. Es mínimo si no hay otra cobertura de vértices con menos vértices. Un gráfico bien cubierto es aquel en el que cada cobertura mínima también es mínima. En el artículo original que define gráficas bien cubiertas, Plummer (1970) escribe que esto es "obviamente equivalente" a la propiedad de que cada dos cubiertas mínimas tienen el mismo número de vértices entre sí.
Un conjunto independiente en un gráfico es un conjunto de vértices de los cuales no hay dos adyacentes entre sí. Si C es una cobertura de vértice en un gráfico G , el complemento de C debe ser un conjunto independiente y viceversa. C es una cobertura de vértice mínima si y solo si su complemento I es un conjunto independiente máximo, y C es una cobertura de vértice mínima si y solo si su complemento es un conjunto independiente máximo. Por lo tanto, un gráfico bien cubierto es, de manera equivalente, un gráfico en el que cada conjunto independiente máximo tiene el mismo tamaño, o un gráfico en el que cada conjunto independiente máximo es máximo. [1]
En el artículo original que definía gráficos bien cubiertos, estas definiciones estaban restringidas a gráficos conectados , [2] aunque también son significativas para gráficos desconectados. Algunos autores posteriores han reemplazado el requisito de conectividad con el requisito más débil de que un gráfico bien cubierto no debe tener vértices aislados. [3] Tanto para gráficos bien cubiertos conectados como para gráficos bien cubiertos sin vértices aislados, no puede haber vértices esenciales , vértices que pertenecen a cada cobertura mínima de vértices. [2] Además, cada gráfico bien cubierto es un gráfico crítico para la cobertura de vértices en el sentido de que, para cada vértice v , eliminar v del gráfico produce un gráfico con una cobertura de vértice mínima más pequeña. [2]
El complejo de la independencia de un gráfico G es el simplicial complejo que tiene un simplex para cada conjunto independiente en G . Se dice que un complejo simplicial es puro si todos sus simples máximos tienen la misma cardinalidad, por lo que un gráfico bien cubierto es equivalentemente un gráfico con un complejo de independencia puro. [4]
Ejemplos de
a | B | C | D | mi | F | gramo | h | ||
8 | ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() | 8 | |||||||
7 | 7 | ||||||||
6 | 6 | ||||||||
5 | 5 | ||||||||
4 | 4 | ||||||||
3 | 3 | ||||||||
2 | 2 | ||||||||
1 | 1 | ||||||||
a | B | C | D | mi | F | gramo | h |
Un gráfico de ciclo de longitud cuatro o cinco está bien cubierto: en cada caso, cada conjunto máximo independiente tiene un tamaño dos. Un ciclo de longitud siete y un camino de longitud tres también están bien cubiertos. Cada gráfico completo está bien cubierto: cada conjunto independiente máximo consta de un solo vértice. De manera similar, todos los gráficos de conglomerados (una unión disjunta de gráficos completos) están bien cubiertos. Un gráfico bipartito completo está bien cubierto si los dos lados de su bipartición tienen el mismo número de vértices, ya que estos son sus únicos dos conjuntos independientes máximos. El gráfico de una torre está bien cubierto: si uno coloca cualquier conjunto de torres en un tablero de ajedrez de modo que no haya dos torres que se ataquen entre sí, siempre es posible continuar colocando más torres que no ataquen hasta que haya una en cada fila y columna del tablero. tablero de ajedrez.
Si P es un polígono o un conjunto de puntos, S es el conjunto de segmentos de línea abiertos que tienen vértices de P como puntos finales y, por lo demás, están separados de P , y G es la gráfica de intersección de S (una gráfica que tiene un vértice para cada segmento de línea en S y un borde para cada dos segmentos de línea que se cruzan), entonces G está bien cubierto. Porque en este caso, todo conjunto independiente máximo en G corresponde al conjunto de aristas en una triangulación de P , y un cálculo que involucra la característica de Euler muestra que cada dos triangulaciones tienen el mismo número de aristas entre sí. [5]
Si G es cualquier gráfico de n -vértices, entonces el producto con raíz de G con un gráfico de un borde (es decir, el gráfico H formado al agregar n nuevos vértices a G , cada uno de grado uno y cada uno adyacente a un vértice distinto en G ) está bien cubierto. Porque, un conjunto independiente máximo en H debe consistir en un conjunto independiente arbitrario en G junto con los vecinos de grado uno del conjunto complementario y, por lo tanto, debe tener un tamaño n . [6] De manera más general, dado cualquier gráfico G junto con una cubierta de clique (una partición p de los vértices de G en cliques), el gráfico G p formado al agregar otro vértice a cada clique está bien cubierto; el producto enraizado es el caso especial de esta construcción cuando p consta de n camarillas de un vértice. [7] Por lo tanto, cada gráfico es un subgráfico inducido de un gráfico bien cubierto.
Bipartita, gráficos muy bien cubiertos y circunferencia
Favaron (1982) define un gráfico muy bien cubierto como un gráfico bien cubierto (posiblemente desconectado, pero sin vértices aislados) en el que cada conjunto máximo independiente (y por lo tanto también cada cobertura mínima de vértice) contiene exactamente la mitad de los vértices. Esta definición incluye los productos enraizados de un gráfico G y un gráfico de un borde. También incluye, por ejemplo, los gráficos bipartitos bien cubiertos estudiados por Ravindra (1977) y Berge (1981) : en un gráfico bipartito sin vértices aislados, ambos lados de cualquier bipartición forman conjuntos independientes máximos (y cubiertas de vértices mínimas), por lo que si el gráfico está bien cubierto, ambos lados deben tener el mismo número de vértices. En un gráfico bien cubierto con n vértices, el tamaño de un conjunto independiente máximo es como máximo n / 2 , por lo que los gráficos bien cubiertos son los gráficos bien cubiertos en los que el tamaño máximo del conjunto independiente es lo más grande posible. [8]
Un gráfico bipartito G está bien cubierto si y solo si tiene una coincidencia perfecta M con la propiedad de que, para cada borde uv en M , el subgrafo inducido de los vecinos de u y v forma un gráfico bipartito completo . [9] La caracterización en términos de emparejamientos puede extenderse desde gráficos bipartitos a gráficos muy bien cubiertos: un gráfico G está muy bien cubierto si y solo si tiene un emparejamiento perfecto M con las siguientes dos propiedades:
- Ningún borde de M pertenece a un triángulo en G , y
- Si un borde de M es el borde central de una ruta de tres bordes en G , entonces los dos puntos finales de la ruta deben ser adyacentes.
Además, si G está muy bien cubierto, entonces cada coincidencia perfecta en G satisface estas propiedades. [10]
Los árboles son un caso especial de grafos bipartitos, y probar si un árbol está bien cubierto puede manejarse como un caso especial mucho más simple de caracterización de 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 no foliar del árbol es adyacente exactamente a una hoja. [9] La misma caracterización se aplica a las gráficas que son localmente similares a árboles, en el sentido de que las vecindades de bajo diámetro de cada vértice son acíclicas: si una gráfica tiene una circunferencia de ocho o más (de modo que, para cada vértice v , el subgrafo de vértices dentro de la distancia tres de v es acíclico) entonces está bien cubierto si y solo si cada vértice de grado mayor que uno tiene exactamente un vecino de grado uno. [11] Una caracterización estrechamente relacionada pero más compleja se aplica a gráficos bien cubiertos de circunferencia cinco o más. [12]
Regularidad y planaridad
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/5/50/3r3c_well-covered.svg/400px-3r3c_well-covered.svg.png)
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/7/74/3r1c_well-covered.svg/240px-3r1c_well-covered.svg.png)
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/e/e2/Snub_disphenoid.png/220px-Snub_disphenoid.png)
Los gráficos cúbicos ( 3 regulares ) bien cubiertos se han clasificado: constan de siete ejemplos conectados a 3 , junto con tres familias infinitas de gráficos cúbicos con menor conectividad. [13]
Los siete gráficos cúbicos bien cubiertos de 3 conexiones son el gráfico completo K 4 , los gráficos del prisma triangular y el prisma pentagonal , el gráfico de Durero , el gráfico de utilidad K 3,3 , un gráfico de ocho vértices obtenido del gráfico de utilidad por una transformada Y-Δ , y el gráfico de Petersen generalizado de 14 vértices G (7,2) . [14] De estos gráficos, los primeros cuatro son gráficos planos . Son los únicos cuatro gráficos poliédricos cúbicos (gráficos de poliedros convexos simples ) que están bien cubiertos. Cuatro de los gráficos (los dos prismas, el gráfico de Durero y G (7,2) ) son gráficos de Petersen generalizados.
Los gráficos así cubierto cúbicos conectados-2 de 1 y están formados por la sustitución de los nodos de un camino o ciclo por tres fragmentos de gráficos que Plummer (1993) labels A , B , y C . Los fragmentos A o B se pueden usar para reemplazar los nodos de un ciclo o los nodos interiores de una ruta, mientras que el fragmento C se usa para reemplazar los dos nodos finales de una ruta. El fragmento A contiene un puente , por lo que el resultado de realizar este proceso de reemplazo en una ruta y usar el fragmento A para reemplazar algunos de los nodos de la ruta (y los otros dos fragmentos para los nodos restantes) es un cúbico bien cubierto de 1 vértice conectado grafico. Todas las gráficas bien cubiertas cúbicas conectadas a 1 vértice tienen esta forma, y todas esas gráficas son planas. [13]
Hay dos tipos de gráficos cúbicos bien cubiertos de 2 vértices conectados. Una de estas dos familias se forma reemplazando los nodos de un ciclo por los fragmentos A y B , siendo al menos dos de los fragmentos de tipo A ; un gráfico de este tipo es plana si y sólo si no contiene ningún fragmentos de tipo B . La otra familia se forma reemplazando los nodos de un camino por fragmentos de tipo B y C ; todos estos gráficos son planos. [13]
Complementando la caracterización de poliedros simples bien cubiertos en tres dimensiones, los investigadores también han considerado los poliedros simpliciales bien cubiertos , o equivalentemente los gráficos planos máximos bien cubiertos. Cada gráfico plano máximo con cinco o más vértices tiene conectividad de vértice 3, 4 o 5. [15] No hay gráficos planos máximos de 5 conectados bien cubiertos, y solo hay cuatro gráficos planos planos máximos bien cubiertos de 4 conectados: las gráficas del octaedro regular , la bipirámide pentagonal , el difenoide chato y un poliedro irregular (un deltaedro no convexo ) con 12 vértices, 30 aristas y 20 caras triangulares. Sin embargo, hay infinitas gráficas planas máximas bien cubiertas con 3 conexiones. [16] Por ejemplo, un gráfico plano máximo bien cubierto de 3 conectados se puede obtener a través de la construcción de la cubierta de clique [7] a partir de cualquier gráfico plano máximo de 3 t -vértices en el que hay t caras de triángulos disjuntos agregando t nuevos vértices, uno dentro de cada una de estas caras.
Complejidad
Probar si un gráfico contiene dos conjuntos máximos independientes de diferentes tamaños es NP-completo ; es decir, de forma complementaria, comprobar si un gráfico está bien cubierto es coNP-completo. [17] Aunque es fácil encontrar conjuntos máximos independientes en gráficos que se sabe que están bien cubiertos, también es NP-difícil que un algoritmo produzca como salida, en todos los gráficos, un conjunto máximo independiente o una garantía de que la entrada no está bien cubierta. [18]
Por el contrario, es posible probar si un gráfico G dado está muy bien cubierto en tiempo polinomial . Para hacerlo, encuentre el subgrafo H de G que consta de los bordes que satisfacen las dos propiedades de un borde coincidente en un gráfico muy bien cubierto, y luego use un algoritmo de coincidencia para probar si H tiene una coincidencia perfecta. [10] Algunos problemas NP-completos para gráficos arbitrarios, como el problema de encontrar un ciclo hamiltoniano , también pueden resolverse en tiempo polinómico para gráficos muy bien cubiertos. [19]
Se dice que un gráfico es equiparable si cada coincidencia máxima es máxima; es decir, es equiparable si su gráfico lineal está bien cubierto. Es posible probar si un gráfico lineal, o más generalmente un gráfico sin garras , está bien cubierto en tiempo polinomial. [20]
Las caracterizaciones de gráficos bien cubiertos con una circunferencia de cinco o más, y de gráficos bien cubiertos que son 3 regulares, también conducen a algoritmos de tiempo polinomial eficientes para reconocer estos gráficos. [21]
Notas
- ^ Plummer (1993) .
- ↑ a b c Plummer (1970) .
- ^ Favaron (1982) .
- ^ Para obtener ejemplos de artículos que utilizan esta terminología, consulte Dochtermann & Engström (2009) y Cook & Nagel (2010) .
- ^ Greenberg (1993) .
- ^ Esta clase de ejemplos fue estudiada por Fink et al. (1985) ; también son (junto con el ciclo de cuatro aristas, que también está bien cubierto) exactamente los gráficos cuyo número de dominación es n / 2 . Su propiedad de buena cobertura también se establece en una terminología diferente (que tiene un complejo de independencia puro) como el Teorema 4.4 de Dochtermann & Engström (2009) .
- ↑ a b Cook y Nagel (2010) .
- ^ Berge (1981) .
- ↑ a b Ravindra (1977) ; Plummer (1993) .
- ↑ a b Staples (1975) ; Favaron (1982) ; Plummer (1993) .
- ^ Finbow y Hartnell (1983) ; Plummer (1993) , Teorema 4.1.
- ^ Finbow y Hartnell (1983) ; Plummer (1993) , Teorema 4.2.
- ↑ a b c Campbell (1987) ; Campbell y Plummer (1988) ; Plummer (1993) .
- ^ Campbell (1987) ; Finbow, Hartnell y Nowakowski (1988) ; Campbell, Ellingham y Royle (1993) ; Plummer (1993) .
- ^ Las gráficas completas en 1, 2, 3 y 4 vértices son todas planas máximas y están bien cubiertas; su conectividad de vértice es ilimitada o como máximo tres, dependiendo de los detalles de la definición de conectividad de vértice que son irrelevantes para gráficos planos máximos más grandes.
- ^ Finbow, Hartnell y Nowakowski et al. ( 2003 , 2009 , 2010 ).
- ^ Sankaranarayana y Stewart (1992) ; Chvátal y Slater (1993) ; Caro, Sebő y Tarsi (1996) .
- ^ Raghavan y Spinrad (2003) .
- ^ Sankaranarayana y Stewart (1992) .
- ^ Lesk, Plummer y Pulleyblank (1984) ; Tankus y Tarsi (1996) ; Tankus y Tarsi (1997) .
- ^ Campbell, Ellingham y Royle (1993) ; Plummer (1993) .
Referencias
- Berge, Claude (1981), "Algunas propiedades comunes para gráficos regularizables, gráficos de bordes críticos y gráficos B ", teoría de grafos y algoritmos (Proc. Sympos., Res. Inst. Electr. Comm., Tohoku Univ., Sendai, 1980) , Lecture Notes in Computer Science, 108 , Berlín: Springer, págs. 108-123, doi : 10.1007 / 3-540-10704-5_10 , ISBN 978-3-540-10704-0, MR 0622929.
- Campbell, SR (1987), Algunos resultados sobre gráficos planos bien cubiertos , Ph.D. tesis, Universidad de Vanderbilt, Departamento de Matemáticas. Como lo cita Plummer (1993) .
- Campbell, SR; Ellingham, MN ; Royle, Gordon F. (1993), "Una caracterización de gráficos cúbicos bien cubiertos", Journal of Combinatorial Mathematics and Combinatorial Computing , 13 : 193-212, MR 1220613.
- Campbell, Stephen R .; Plummer, Michael D. (1988), "Sobre 3 politopos bien cubiertos", Ars Combinatoria , 25 (A): 215–242, MR 0942505.
- Caro, Yair; Sebő, András ; Tarsi, Michael (1996), "Reconociendo estructuras codiciosas", Journal of Algorithms , 20 (1): 137-156, doi : 10.1006 / jagm.1996.0006 , MR 1368720.
- Chvátal, Václav ; Slater, Peter J. (1993), "Una nota sobre gráficos bien cubiertos", Quo vadis, teoría de grafos? , Annals of Discrete Mathematics, 55 , Amsterdam: North-Holland, págs. 179–181, MR 1217991.
- Cook, David, II; Nagel, Uwe (2010), "Cohen-Macaulay graphs and face vectors of flag complexes", SIAM Journal on Discrete Mathematics , 26 : 89–101, arXiv : 1003.4447 , Bibcode : 2010arXiv1003.4447C , doi : 10.1137 / 100818170.
- Dochtermann, Anton; Engström, Alexander (2009), "Propiedades algebraicas de los ideales de los bordes a través de la topología combinatoria" , Electronic Journal of Combinatorics , 16 (2): Documento de investigación 2, MR 2515765.
- Favaron, O. (1982), "Gráficos muy bien cubiertos", Matemáticas discretas , 42 (2-3): 177-187, doi : 10.1016 / 0012-365X (82) 90215-1 , MR 0677051.
- Finbow, AS; Hartnell, BL (1983), "Un juego relacionado con la cobertura de estrellas", Ars Combinatoria , 16 (A): 189-198, MR 0737090.
- Finbow, A .; Hartnell, B .; Nowakowski, R. (1988), "Gráficos bien dominados: una colección de gráficos bien cubiertos", Ars Combinatoria , 25 (A): 5–10, MR 0942485.
- Finbow, A .; Hartnell, B .; Nowakowski, RJ (1993), "Una caracterización de gráficos bien cubiertos de circunferencia 5 o mayor", Journal of Combinatorial Theory , Serie B, 57 (1): 44-68, doi : 10.1006 / jctb.1993.1005 , MR 1198396.
- Finbow, A .; Hartnell, B .; Nowakowski, R .; Plummer, Michael D. (2003), "Sobre triangulaciones bien cubiertas. I", Matemáticas aplicadas discretas , 132 (1-3): 97-108, doi : 10.1016 / S0166-218X (03) 00393-7 , MR 2024267.
- Finbow, Arthur S .; Hartnell, Bert L .; Nowakowski, Richard J .; Plummer, Michael D. (2009), "Sobre triangulaciones bien cubiertas. II", Matemáticas aplicadas discretas , 157 (13): 2799-2817, doi : 10.1016 / j.dam.2009.03.014 , MR 2537505.
- Finbow, Arthur S .; Hartnell, Bert L .; Nowakowski, Richard J .; Plummer, Michael D. (2010), "Sobre triangulaciones bien cubiertas. III", Matemáticas aplicadas discretas , 158 (8): 894–912, doi : 10.1016 / j.dam.2009.08.002 , MR 2602814.
- Fink, JF; Jacobson, MS; Kinch, LF; Roberts, J. (1985), "Sobre gráficos que tienen un número de dominación la mitad de su orden", Period. Matemáticas. Hungar. , 16 (4): 287–293, doi : 10.1007 / BF01848079 , MR 0833264.
- Greenberg, Peter (1993), "Piecewise SL 2 Z geometry", Transactions of the American Mathematical Society , 335 (2): 705–720, doi : 10.2307 / 2154401 , JSTOR 2154401 , MR 1140914.
- Lesk, M .; Plummer, MD ; Pulleyblank, WR (1984), "Gráficos equiparables", Teoría de grafos y combinatoria (Cambridge, 1983) , Londres: Academic Press, págs. 239-254, MR 0777180.
- Plummer, Michael D. (1970), "Algunos conceptos que cubren los gráficos", Journal of Combinatorial Theory , 8 : 91–98, doi : 10.1016 / S0021-9800 (70) 80011-4 , MR 0289347.
- Plummer, Michael D. (1993), "Gráficos bien cubiertos: una encuesta" , Quaestiones Mathematicae , 16 (3): 253–287, doi : 10.1080 / 16073606.1993.9631737 , MR 1254158.
- Raghavan, Vijay; Spinrad, Jeremy (2003), "Algoritmos robustos para dominios restringidos", Journal of Algorithms , 48 (1): 160–172, doi : 10.1016 / S0196-6774 (03) 00048-8 , MR 2006100.
- Ravindra, G. (1977), "Gráficos bien cubiertos", Journal of Combinatorics, Information and System Sciences , 2 (1): 20-21, MR 0469831.
- Sankaranarayana, Ramesh S .; Stewart, Lorna K. (1992), "Resultados de complejidad para gráficos bien cubiertos", Networks , 22 (3): 247-262, CiteSeerX 10.1.1.47.9278 , doi : 10.1002 / net.3230220304 , MR 1161178.
- Staples, J. (1975), Sobre algunas subclases de gráficos bien cubiertos , Ph.D. tesis, Universidad de Vanderbilt, Departamento de Matemáticas. Como lo cita Plummer (1993) .
- Tankus, David; Tarsi, Michael (1996), "Gráficos sin garras bien cubiertos", Journal of Combinatorial Theory , Serie B, 66 (2): 293–302, doi : 10.1006 / jctb.1996.0022 , MR 1376052.
- Tankus, David; Tarsi, Michael (1997), "La estructura de gráficos bien cubiertos y la complejidad de sus problemas de reconocimiento", Journal of Combinatorial Theory , Serie B, 69 (2): 230-233, doi : 10.1006 / jctb.1996.1742 , MR 1438624.