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
Diámetro
Cintura
Automorfismos
Número cromático 2
Índice cromático max{m, n}

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 editar

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.[1]

El grafo completo bipartito con particiones de tamaño   y   es denotado como  .[1]

Ejemplos editar


Propiedades editar

Sea   un grafo bipartito con   y  , se verifica:[cita requerida]

  •  
  •   posee   árboles de expansión.

Véase también editar

Referencias editar

  1. a b c d Wasserman y Faust, 2013, «Grafos y matrices» (por Dawn Iacobucci), pp. 121-188.

Bibliografía editar

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