¿Es correcta esta definición de grafo bipartito completo?

Question

El libro que estoy utilizando definió un gráfico completo $K_{m,n} = \overline{K}_m + \overline{K}_n$ . ¿Es esto correcto? Estoy confundido ya que el complemento de un grafo completo es un grafo vacío. ¿Cómo es la adición de dos grafos vacíos un grafo bipartito completo si seguimos la definición?

Answer 1

Algunos autores utilizan $G+H$ para indicar el unión de gráficos que es una copia de $G$ y una copia de $H$ junto con cada arista entre $G$ y $H$ . Esto es desafortunado para la OMI, ya que $+$ tiene más sentido como unión disjunta. (Los autores que utilizan $+$ para la unión probablemente utilice $G\cup H$ o $G\sqcup H$ para la unión disjunta).

Answer 2

Parece que en su libro la notación $G_1 + G_2$ se refiere a la gráfica obtenida de la siguiente manera: tomar las gráficas $G_1$ y $G_2$ y unir cada vértice en $G_1$ a cada vértice de $G_2$ .

Así, si tomamos el gráfico vacío en $m$ vértices $x_1,\ldots,x_m$ y el gráfico vacío en $n$ vértices $y_1,\ldots,y_n$ y unir cada $x_i$ a cada $y_j$ obtenemos el gráfico $K_{m,n}$ .