Grafo bipartito completo

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]

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]​

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]​

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]​

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

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.

• Grafo bipartito
• Grafo completo

• Wasserman, Stanley; Faust, Katherine (2013) [1994]. Análisis de redes sociales: Métodos y aplicaciones. Madrid: Centro de Investigaciones Sociológicas. ISBN 978-84-7476-631-8. OCLC 871814053.