Garra y co-garra de los gráficos gratuitos

Question

Supongamos que queremos definir la clase de garra y co-garra de los gráficos gratuitos? Las gráficas de G tales que ni G ni su complemento contiene un inducida por la garra ($K_{1,3}$).

Hacer estos gráficos tienen ningún tipo de interesante estructura, además de lo que ya está implícito? ¿Qué sería de los buenos ejemplos? Hasta ahora no puedo pensar en ciclos, $K_n$ menos de un borde, cóctel de gráficos (http://mathworld.wolfram.com/CocktailPartyGraph.html). También la casa de la gráfica de ( $C_5$ , además de un borde), y algunos otros pequeños gráficos. (Y sus complementos, por supuesto).

Answer 1

Una forma fácil de entender subclase de estos son los $\{K_3,K_{1,3}\}$libre de gráficos. (Estos son una subclase porque $K_3$ es un subgrafo de $\overline{K_{1,3}}$.)

Los gráficos de este tipo puede tener un máximo de grado $2$, porque si un vértice $v$ tiene vecinos,$w_1,w_2,w_3$, entonces son independientes (y formar una $K_{1,3}$ junto con $v$) o hay un borde de $w_i w_j$ (que forma un triángulo junto con $v$). Así, podemos clasificar estas completamente: son los distintos sindicatos de islated vértices, los caminos, y los ciclos de longitud de, al menos,$4$.

Del mismo modo, los complementos de estos gráficos con una buena subclase, el $\{\overline{K_3},\overline{K_{1,3}}\}$libre de gráficos, que ahora también entiendo.

Ahora voy a demostrar que estos son los únicos casos cuando el número de vértices es suficientemente grande (al menos $11$).

En general $\{K_{1,3},\overline{K_{1,3}}\}$libre de gráfico, en el barrio de $N(v)$ de cualquier vértice $v$ $\{\overline{K_3},\overline{K_{1,3}}\}$libre, y la co-vecindad $\overline{N}(v)$ $\{K_3,K_{1,3}\}$- libre. Pero estos no pueden ser grandes. Siempre que $w \in N(v)$ tiene vecinos,$x_1,\dots,x_k$$\overline{N}(v)$, $x_1, \dots, x_k$ debe formar una camarilla: si $x_ix_j$ no es un borde, luego se $\{w,x_i,x_j,v\}$ inducir una $K_{1,3}$. Pero $\overline{N}(v)$ $K_3$libre, por lo $k \le 2$. y hay en la mayoría de las $2|N(v)|$ bordes entre las $N(v)$$\overline{N}(v)$.

Del mismo modo, existen en la mayoría de las $2|\overline{N}(v)|$ sin bordes. Pero hay $|N(v)| \cdot |\overline{N}(v)|$ pares de vértices aquí, que son bordes o no los bordes. Así $$|N(v)| \cdot |\overline{N}(v)| \le 2|N(v)| + 2|\overline{N}(v)| \iff (|N(v)|-2)(|\overline{N}(v)|-2) \le 4.$$

Supongamos que la gráfica es de gran tamaño (ha $n>10$ vértices). Entonces la única manera de satisfacer esta desigualdad es asegurarse de que cada vértice tiene grado o co-grado $2$. Pero si hay un vértice $v$ con grado en la mayoría de las $2$, y un vértice $w$ con co-grado en la mayoría de las $2$, entonces no se $n-5$ vértices adyacentes a $w$ pero no $v$, y entre estos vértices no puede ser un $K_3$ o $\overline{K_3}$. Esto es imposible por el teorema de Ramsey.

Así, aparte de pequeños ejemplos, estos gráficos tienen su grado máximo $2$ o máximo de co-grado $2$, y ya hemos descubierto lo que estos dos casos son similares.

El ejemplo más grande que he encontrado no de este tipo es el Paley gráfico en $9$ vértices,

que se puede encontrar en la Casa de los Gráficos aquí. (Como todos los Paley gráficos, es la auto-complementarios, por lo que es suficiente para comprobar que la uña libre, que lo es.) No tengo una prueba de que no hay $10$-vértice ejemplo.