Gráfico bipartito completo

Un grafo bipartito completo ( biklik ) es un tipo especial de grafo bipartito en el que cualquier vértice de la primera parte está conectado a todos los vértices de la segunda parte de los vértices.

Definición

Un grafo bipartito completo es un grafo bipartito tal que para dos vértices cualesquiera y , es una arista en . Un gráfico bipartito completo con partes de tamaño y se denota como . $G:=(V_{1}+V_{2},E)$ $v_{1}\en V_{1}$ $v_{2}\en V_{2}$ $(v_{1},v_{2})$ $GRAMO$ $|V_{1}|=m$ $|V_{2}|=n$ $K_{{m, n}}$

Ejemplos

Los gráficos se llaman estrellas , todos los gráficos bipartitos completos que son árboles son estrellas. $K_{{1,k}}$
El gráfico se denomina garra y se utiliza para definir gráficos sin garras . $K_{{1,3}}$
El gráfico a veces se denomina "gráfico comunal", el nombre se remonta al problema clásico de " casas y pozos ", en una interpretación moderna que utiliza la formulación "comunal" (conectar tres casas al agua, la electricidad y el gas sin cruzar las líneas en el plano); el problema no tiene solución debido a la no planaridad del gráfico . $K_{{3,3}}$ $K_{{3,3}}$

Propiedades

El problema de encontrar, para un grafo bipartito dado, un subgrafo bipartito completo con un parámetro dado es NP-completo . $K_{{n,n}}$ $norte$
Un grafo plano no puede contener un grafo como menor . Un gráfico plano exterior no puede contener como un menor (Esta no es una condición suficiente para la planaridad y la planaridad exterior, pero es necesaria). Por el contrario, cualquier gráfico no plano contiene , o el gráfico completo como un menor ( teorema de Pontryagin-Kuratovsky ). $K_{{3,3}}$ $K_{{3,2}}$ $K_{{3,3}}$ $K_{5}$
Los gráficos bipartitos completos son gráficos y celdas de Moore . $K_{{n,n}}$ $(n,4)$
Los gráficos bipartitos completos son los gráficos de Turan . $K_{{n,n}}$ $K_{{n,n+1}}$
Un gráfico bipartito completo tiene un tamaño de cobertura de vértices y un tamaño de cobertura de bordes . $K_{{m, n}}$ $\min(m,n)$ $\max(m,n)$
Un gráfico bipartito completo tiene un conjunto independiente máximo de tamaño . $K_{{m, n}}$ $\max(m,n)$
La matriz de adyacencia de un grafo bipartito completo tiene valores propios , y con multiplicidades , y , respectivamente. $K_{{m, n}}$ ${\ sqrt{nm))$ $-{\raíz cuadrada{nm))$ ${\ estilo de visualización 0}$ $una$ $una$ $n+m-2$
La matriz de Laplace de un grafo bipartito completo tiene valores propios , , , con multiplicidades , y respectivamente. $K_{{m, n}}$ $n+m$ $norte$ $metro$ ${\ estilo de visualización 0}$ $una$ $m-1$ $n-1$ $una$
Un grafo bipartito completo tiene árboles de expansión . $K_{{m, n}}$ $m^{{n-1}}\cdot n^{{m-1}}$
Un gráfico bipartito completo tiene una coincidencia máxima de tamaño . $K_{{m, n}}$ $\min(m,n)$
Un grafo bipartito completo tiene un color de borde adecuado correspondiente al cuadrado latino . $K_{{n,n}}$ $norte$

Los dos últimos resultados son consecuencia del teorema de Hall aplicado a un grafo bipartito -regular . $k$

Véase también

Literatura

John Adrian Bondy, USR Murty. Teoría de Grafos con Aplicaciones. - Holanda Septentrional, 1976. - P. 5 . — ISBN 0-444-19451-7 . Archivado desde el original el 13 de abril de 2010.
Reinhard Diestel. Teoría de grafos // 3er. - Springer , 2005. - S. 17 . — ISBN 3-540-26182-6 .