Gráficos donde el cambio de cualquier borde aumenta el número de camarilla o independencia

Question

Tome el ciclo en$5$ vértices,$C_5$. El número de camarilla e independencia de este gráfico son$2$. Si añadimos cualquier arista a$C_5$ obtendremos un triángulo. Mientras tanto, si eliminamos cualquier borde obtenemos un triángulo en el complemento.

Así que cualquiera que sea el borde que cambiemos, obtendremos un aumento (del$2$ al$3$) del número de la pandilla, o del número de la independencia. ¿Es$C_5$ el único gráfico con esta propiedad, o hay otros?

Answer 1

Buena pregunta! No, este no es el único ejemplo no trivial. Tome $p=13$ y construir el grafo cuyos vértices son el residuo de las clases de mod $p$, con una arista entre dos cuya diferencia es un residuo cuadrático. Esto está bien definido (porque $p\equiv 1\pmod 4$, $x-y$ es una ecuación cuadrática de residuos si y sólo si $y-x$ es).

El gráfico es el borde transitiva, ya que $x\mapsto a^2x+b$ es un automorphism para cualquier $a,b\in \mathbb Z_p$ $a\neq 0.$ es también auto-complementarios (multiplicar por cualquier cuadrática no-residuo). Por lo tanto, es suficiente para mostrar que la adición de un poco de borde (dicen $0$-$2$) aumenta la camarilla número. La camarilla número es $3$: la única vértices que forman un triángulo con $0$-$1$ se $10$$4$, y estos cuatro vértices no forman un grupo cerrado, por lo que $0$-$1$ no está en un clique de tamaño $4$ (y por transitividad tampoco lo es cualquier otra orilla). Pero si $0$-$2$ se añade, a continuación,$12$-$0$-$2$-$3$ es un clique de tamaño $4$.

Bien puede ser que esta construcción funciona para cualquier prime $p\equiv 1\pmod 4,$ pero no puedo ver cómo probar que.

Answer 2

Aquí hay un par de gráficos de su propiedad.

Deje $\alpha(G),\ \omega(G),$ $n(G)$ denotar el número de independencia, la camarilla número, y el orden de un (finito) gráfico de $G.$

El número de Ramsey $R(s,t)$ está definido por la propiedad de que la $R(s,t)-1$ es el máximo posible orden de un gráfico de $G$$\alpha(G)\lt s$$\omega(G)\lt t.$, con Lo que, por definición (y por Ramsey del teorema que nos dice que $R(s,t)$ existe), no hay un gráfico de $G_{s,t}$ (no necesariamente único) tal que $\alpha(G_{s,t})=s-1,\ \omega(G_{s,t})=t-1,$ $n(G_{s,t})=R(s,t)-1.$ En algunos casos un gráfico de $G_{s,t}$ tendrá su propiedad:

Lema. Si $R(s,t)=R(s-1,t)+R(s,t-1),$ $G_{s,t}$ tiene la propiedad de que la eliminación de cualquier borde aumentará el número de independencia, mientras que la adición de cualquier borde aumentará la camarilla número.

Prueba. El gráfico de $G=G_{s,t}$ es regular de grado $R(s,t-1)-1.$ Agregar un borde a $uv$ va a crear un vértice $v$ grado $R(s,t-1).$ Desde $\alpha(G+uv)\le\alpha(G)\lt s,$ se sigue que $v$ $t$- camarilla de $G+uv,$ $\omega(G+uv)\ge t\gt\omega(G).$ del mismo modo, la eliminación de un borde aumentará el número de independencia.

Es un básico lema en Ramsey teoría de que la desigualdad de $R(s,t)\le R(s-1,t)+R(s,t-1)$ siempre tiene; parece que la desigualdad es generalmente estricta, pero la igualdad de los casos nos dan los gráficos de su propiedad.

Ejemplos:

$R(3,3)=6=3+3=R(2,3)+R(3,2);\ G_{3,3}=C_5.$

$R(n+1,2)=n+1=R(n,2)+R(n+1,1);\ G_{n+1,2}=K_n.$

$R(2,n+1)=n+1=R(2,n)+R(1,n+1);\ G_{2,n+1}=\overline{K_n}.$

$R(3,5)=14=5+9=R(2,5)+R(3,4);$ $G_{3,5}$ podemos tomar $C_{13}$ y añadir todos los acordes de la longitud de la $5.$

$R(4,4)=18=9+9=R(3,4)+R(4,3);$ ver esta pregunta o cualquier libro de texto sobre la teoría de Ramsey.