Lo sé. $K_{n,n,n}$ está determinado por su espectro de adyacencia (utilizando su regularidad) y sé que los grafos multipartitos completos no están determinados por sus espectros de adyacencia, en general. ¿Qué pasa con $K_{1,n,n}$ y $K_{1,1,n}$ (grafos tripartitos completos)? ¿están determinados por los espectros de sus matrices de adyacencia? Creo que son DS (determinados por el espectro de adyacencia) pero no encuentro una referencia para ello ni lo pruebo. ¿Alguien sabe si hay una referencia para esto? ¿O una referencia para grafos tripartitos completos? Gracias a todos por la ayuda.
Respuesta
¿Demasiados anuncios?
Desde el espectro de $K_{1,n,n}$ o $K_{1,1,n}$ podemos determinar:
- Que un grafo con ese espectro es un grafo multipartito completo, posiblemente con vértices aislados añadidos. (Este tipo de grafos son los únicos que tienen exactamente un valor propio positivo; véase, por ejemplo, esta pregunta .)
- Que de hecho el componente multipartito completo es un gráfico tripartito $K_{a,b,c}$ por el número de valores propios no nulos. (Los vértices aislados sólo sumarán algún número de $0$ valores propios).
- También sabemos que $ab+ac+bc$ el número de aristas del $K_{a,b,c}$ debe coincidir con el número de aristas en $K_{1,n,n}$ o $K_{1,1,n}$ respectivamente. El recuento de aristas viene determinado por los valores propios.
Esser y Harary's Sobre el espectro de un grafo multipartito completo nos dice más: los valores propios negativos de $K_{a,b,c}$ con $a \le b \le c$ son $\lambda_{a+b+c-1} \in [-b,-a]$ y $\lambda_{a+b+c} \in [-c,-b]$ . También dan algunas garantías de rigor, de las cuales sólo necesitamos una: si $a < b$ entonces $\lambda_{a+b+c-1} \in (-b,-a)$ .
Esto es suficiente para hacer frente a $K_{1,1,n}$ que tiene un valor propio de $-1$ . Para $K_{a,b,c}$ para tener un valor propio de $-1$ Debemos tener $a=1$ (ya que $\lambda_{a+b+c-1} \le -a$ ) y $b=1$ (o bien $\lambda_{a+b+c-1} < a$ ). Pero no $K_{1,1,c}$ con $c \ne n$ tiene el mismo número de aristas que $K_{1,1,n}$ .
Para $K_{1,n,n}$ obtenemos un valor propio negativo de $\frac{n - \sqrt{n^2+8n}}{2} \in (-2,-1]$ por lo que cualquier pareja cospectral potencial con un componente tripartito de $K_{a,b,c}$ debe tener $a=1$ También. Además, el número de aristas debe coincidir con $K_{1,n,n}$ : $b + c + bc = 2n + n^2$ o $(b+1)(c+1) = (n+1)^2$ . Pero de esto se deduce que $b+c\ge 2n$ con igualdad sólo si $b=c=n$ por lo que cualquier otro gráfico tripartito $K_{1,b,c}$ con $2n+n^2$ aristas tiene más vértices que $K_{1,n,n}$ .
De hecho, las parejas cospectrales de grafos tripartitos completos son bastante raras. El ejemplo más pequeño que encontré fue $K_{5,6,20}$ que tiene el mismo espectro que $K_{4,10,15} \cup 2K_1$ . Sin embargo, existen :)
Otra aproximación al problema, una vez que hemos averiguado que buscamos algo de la forma $K_{a,b,c} \cup d K_1$ es calcular el polinomio característico: es $$ \pm x^{a+b+c+d-3}(x^3 - (ab + ac + bc)x - 2abc). $$ Así que $K_{a,b,c}$ y $K_{a',b',c'}$ son "cospectrales hasta los vértices aislados" si $ab + ac + bc = a'b' + a'c' + b'c'$ y $abc = a'b'c'$ .
