Determinar si un gráfico es hamiltoniano

Question

Para $a \geq 1$ determinar si $K_{a,2a,3a}$ o $K_{a,2a,3a+1}$ son Hamiltoniano.

He intentado hacer muchos dibujos durante todo el día pero no puedo resolver el problema. ¿Puede alguien ayudarme con esto? Sé que hay algunos resultados para determinar si una gráfica es hamiltoniana que están todos presentes en mi libro de texto. Por ejemplo, sé que $k(G - S) \leq |S|$ es válida para un grafo hamiltoniano para cada conjunto propio $S$ de vértices.

Hay algunos otros resultados que tengo pero no sé si son útiles en este problema.

Nota: $K_{a, b, c}$ es el gráfico tripartito completo en $a + b + c$ vértices.

Answer 1

En el caso de $K_{a,2a,3a}$ que el $3$ las partes sean $U,V,W,$ con $|U|=a, |V|=2a, |W|=3a$ . Disponga los vértices de $W$ en un círculo. Entre dos de ellos cualesquiera, coloca un vértice de $U\cup V$ . Esta construcción da un ciclo de Hamilton.

En el caso de $K_{a,2a,3a+1}$ Supongamos que hay un ciclo de Hamilton. Sean las partes $U,V,W,$ con $|U|=a$ , $|V|=2a$ , $|W|=3a+1$ . En el ciclo, cada vértice de $W$ es adyacente a $2$ vértices de $U\cup V$ , dando $6a+2$ vértices en $U\cup V$ . Cada vértice en $U\cup V$ se cuenta como máximo dos veces, por lo que hay al menos $3a+1$ vértices en $U\cup V$ contradicción.