Grafo bipartito completo

Grafo bipartito completo
Un grafo bipartito completo con m = 5 y n = 3
Vértices	n + m
Aristas	mn
Radio	$\left\{{\begin{array}{ll}1&m=1\vee n=1\\2&{\text{en otro caso}}\end{array}}\right.$
Diámetro	$\left\{{\begin{array}{ll}1&m=n=1\\2&{\text{en otro caso}}\end{array}}\right.$
Cintura	$\left\{{\begin{array}{ll}\infty &m=1\vee n=1\\4&{\text{en otro caso}}\end{array}}\right.$
Automorfismos	$\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}

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

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

Definición

Un grafo bipartito completo $G:=(V_{1}\cup V_{2},E)\,$ es un grafo bipartito tal que $\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.​

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

Ejemplos

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

Propiedades

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

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

Véase también

• Grafo bipartito
• Grafo completo

Bibliografía

• 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. 

• Datos: Q913598
• Multimedia: Complete bipartite graphs / Q913598