El completo $k$ -Gráfico de la parte $K_{n_1,n_2,\dots,n_k}$ tiene un conjunto de vértices $V=V_1\dot\cup V_2\dot\cup\dots\dot\cup V_k$ , donde $V_1,\dots,V_k$ son conjuntos disjuntos con $|V_i|=n_i$ y cada vértice $v\in V_i$ está conectado a todos los vértices de $V\setminus V_i,i=1,2,\dots,k$ . Describa todos $k$ -tuplas $(n_1,n_2,\dots,n_k)$ de los números naturales, $k=1,2,\dots$ , de tal manera que $K_{n_1,n_2,\dots,n_k}$ es un gráfico plano.
Respuesta
¿Demasiados anuncios?
Technophile
Puntos
101
Todos los planos $k$ -los gráficos parciales deben tener $k<5$ ; si $k\ge5$ el gráfico contendrá la parte no plana $K_{1,1,1,1,1}\simeq K_5$ .
Supongamos ahora que $k=4$ . Los órdenes de partición en un grafo planar de 4 partes deben ser todos menores que 3; $K_{3,1,1,1}$ es no planar por tener $K_{3,3}$ como subgrafo y todos los grafos cuatripartitos con una partición de orden al menos 3 tendrán $K_{3,1,1,1}$ como un subgrafo. Por lo tanto, los órdenes de partición sólo pueden ser uno o dos, pero $K_{2,2,1,1}$ ya es no planar al contener $K_{3,3}$ como un subgrafo. Por lo tanto, los únicos grafos planares de 4 partes son $K_{2,1,1,1}\simeq K_5-e$ y $K_{1,1,1,1}\simeq K_4$ .
Pasando a los gráficos tripartitos, $K_{n,1,1}$ es planar para todos los naturales $n$ pero $K_{3,2,1}$ no es plano porque es $K_{3,3}+e$ . Por tanto, el único grafo tripartito plano con exactamente una partición de orden uno es $K_{2,2,1}$ . Si todas las particiones tienen al menos dos vértices, sólo $K_{2,2,2}$ es planar (es el gráfico octaédrico); $K_{3,2,2}$ es no planar al contener $K_{3,3}$ como un subgrafo.
Gráficos bipartitos $K_{m,n}$ son muy fáciles de caracterizar: son no planas si $m,n\ge3$ . Por último, para una sola partición tenemos simplemente gráficos planos y vacíos.
En resumen, el $k$ -tuplas asociadas con el plano $k$ -son los grafos parciales (donde $n$ es un número natural):
- $k=4$ : $(2,1,1,1),(1,1,1,1)$
- $k=3$ : $(n,1,1),(2,2,2),(2,2,1)$
- $k=2$ : $(n,2),(n,1)$
- $k=1$ : $(n)$
