¿Cuáles son las condiciones para que el complemento de un grafo conexo sea conexo?
En particular, ¿cuándo es el complemento de un grafo regular conectado? Creo que si la regularidad del grafo es $\left\lceil\frac{n-1}{2}\right\rceil$ , su complemento debería estar conectado, aunque es una mera intuición.
"Por cada dos particiones de los vértices en dos grupos debe faltar una arista entre grupos".
$=> $ si hay $\ge 2$ componentes conectados en el gráfico del complemento, entonces podemos agrupar nuestros vértices en dos grupos: {un componente conectado, los otros}. Para el gráfico inicial no falta ninguna arista entre ellos.
$<= $ si el grafo del complemento es conectado, entonces para cada partición hay una arista entre grupos. Y esta arista no existe para la misma pertición en el gráfico inicial.
Probado.
Que la conectividad del grafo del complemento proporciona la condición mencionada para el grafo inicial.
Asumimos que el complemento está desconectado con la condición mencionada, pero donde hay una contradicción que nos lleva a la conectividad del complemento.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
0 votos
¿Cree que existen esas condiciones? Por favor: sea más específico con su pregunta. Podrían existir demasiadas respuestas buenas, pero tal vez usted tenga algo preciso en su mente.
0 votos
@ Crostul, ¡editado!
0 votos
Creo que $K_{m,m}$ (para $m\ge 1$ ) es un contraejemplo a la conjetura particular que has dado en la pregunta; su complemento son dos copias disjuntas de $K_m$ ¿verdad?
0 votos
(El carácter extremo de esta situación sugiere un argumento de recuento: si el gráfico es $k$ -regular con $k < \lceil\frac{n-1}{2}\rceil$ el complemento tendrá demasiadas aristas para ser desconectado. Sin embargo, dudo que esta sea una condición lo suficientemente interesante para ti).
0 votos
@Steven Taschuk, tienes razón. Gracias por señalarlo.
0 votos
¿Por qué "complemento de un conectado ¿Gráfico? El complemento de un grafo desconectado es siempre conectado, así que lo que se pregunta es cuándo es conectado el complemento de un grafo. Pero todo gráfico es el complemento de otro gráfico, así que también podrías preguntar: "¿Cuándo está conectado un gráfico?". O "¿cuándo está conectado un grafo regular?"