Grafo bipartito completo

En teoría de grafos, un grafo bipartito completo es un grafo bipartito en el que todos los vértices de uno de los subconjuntos de la partición están conectados a todos los vértices del segundo subconjunto, y viceversa.^[1]

Grafo bipartito completo
Un grafo bipartito completo con m = 5 y n = 3
Vértices	n + m
Aristas	mn
Radio	${\displaystyle \left\{{\begin{array}{ll}1&m=1\vee n=1\\2&{\text{en otro caso}}\end{array}}\right.}$
Diámetro	${\displaystyle \left\{{\begin{array}{ll}1&m=n=1\\2&{\text{en otro caso}}\end{array}}\right.}$
Cintura	${\displaystyle \left\{{\begin{array}{ll}\infty &m=1\vee n=1\\4&{\text{en otro caso}}\end{array}}\right.}$
Automorfismos	${\displaystyle \left\{{\begin{array}{ll}2m!n!&n=m\\m!n!&{\text{en otro caso}}\end{array}}\right.}$
Número cromático	2
Índice cromático	max{m, n}
[editar datos en Wikidata]

Este concepto se puede generalizar al de grafo s-bipartito completo, como un grafo cuyo conjunto de vértices se puede particionar en s subconjuntos, de modo que todos los pares de vértices pertenecientes a subconjuntos diferentes son adyacentes.^[1]

Definición

Un grafo bipartito completo ${\displaystyle G:=(V_{1}\cup V_{2},E)\,}$ es un grafo bipartito tal que ${\displaystyle \forall v_{1}\in V_{1},\forall \ v_{2}\in V_{2}\Rightarrow e(v_{1},v_{2})\in E.\,}$ Es decir, un grafo bipartito completo está formado por dos conjuntos disjuntos de vértices y todas las posibles aristas que unen esos vértices.^[1]

El grafo completo bipartito con particiones de tamaño ${\displaystyle \left|V_{1}\right|=m}$ y ${\displaystyle \left|V_{2}\right|=n,}$ es denotado como ${\displaystyle K_{m,n}\,}$.^[1]

Ejemplos

• 
  K_3,1 (grafo estrella S₃)
• 
  K_3,2
• 
  K_3,3

Propiedades

Sea ${\displaystyle K_{m,n}\,}$ un grafo bipartito con ${\displaystyle \left|V_{1}\right|=m}$ y ${\displaystyle \left|V_{2}\right|=n}$, se verifica:^{[cita requerida]}

• ${\displaystyle \left|E\right|=\left|V_{1}\right|\cdot \left|V_{2}\right|=m\cdot n}$
• ${\displaystyle K_{m,n}\,}$ posee ${\displaystyle m^{n-1}\cdot n^{m-1}}$ árboles de expansión.

Véase también

• Grafo bipartito
• Grafo completo