Grafo bipartito completo

En teoría de grafos un grafo bipartito (o bipartido) completo es aquel grafo bipartito en el que todos los vértices de la partición están conectados a todos los vértices de la partición y viceversa.

Grafo bipartito completo
Biclique K 3 5.svg
Un grafo bipartito completo con m = 5 y n = 3
Vértices n + m
Aristas mn
Radio
Diámetro
Cintura
Automorfismos
Número cromático 2
Índice cromático max{m, n}

DefiniciónEditar

Un grafo bipartito completo   es un grafo bipartito tal que   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   y   es denotado como  .

EjemplosEditar


PropiedadesEditar

Sea   un grafo bipartito con   y  , se verifica:

  •  
  •   posee   árboles de expansión.

Véase tambiénEditar