Cobertura doble por un gráfico bipartito

La doble cubierta bipartita de un grafo no dirigido G es la cubierta bipartita de G con el doble de vértices que G . La cubierta se puede construir como un producto tensorial de gráficos , G × K 2 . Esta cubierta también se llama la doble cubierta de Kronecker o la doble cubierta canónica del gráfico G.

Esta cobertura no debe confundirse con la cobertura de ciclo doble de un gráfico, una familia de ciclos que incluyen cada borde dos veces.

Edificio

Una doble cubierta bipartita de G tiene dos vértices u i y w i para cada vértice v i de G . Dos vértices u i y w j están conectados por una arista en la cubierta doble si y sólo si vi y v j están conectados por una arista en G . Por ejemplo, a continuación se muestra un dibujo de una doble cubierta bipartita de un gráfico H no bipartito . En la ilustración, cada vértice en el producto tensorial se muestra en color del primer factor ( H ) y la forma del vértice se toma del segundo factor ( K 2 ). Así, los vértices u i en la cubierta doble se muestran como círculos y los vértices w i se muestran como cuadrados.

También se puede construir una cubierta doble bipartita usando matrices de adyacencia (como se describe a continuación) o como un gráfico de tensión derivado en el que cada borde de G está etiquetado con elementos distintos de cero del grupo de dos elementos .

Ejemplos

La doble cubierta bipartita del gráfico de Petersen es el gráfico de Desargues — K 2 × G (5,2)= G (10,3).

La doble cubierta bipartita del grafo completo K n es la corona ( el grafo bipartito completo K n , n menos el emparejamiento perfecto ). En particular, la doble cubierta bipartita del gráfico de tetraedro , K 4 , es el gráfico de cubo .

La doble cobertura bipartita de un ciclo de longitud impar es un ciclo del doble de longitud, mientras que la doble cobertura bipartita de cualquier grafo bipartito (en particular, el ciclo de longitud par que se muestra en la figura) está formada por dos copias del grafo original .

Interpretación matricial

Si un grafo no dirigido G tiene la matriz A como su matriz de adyacencia , entonces la matriz de adyacencia de la doble cubierta bipartita del grafo G es

y la matriz de biadyacencia de la doble cubierta G es la propia matriz A. Es decir, la transformación de un gráfico en su doble cubierta se puede hacer simplemente interpretando A como una matriz de bis-adyacencia en lugar de una matriz de adyacencia. Más generalmente, la interpretación de matrices de adyacencia de grafos dirigidos como matrices bisadyacentes da una equivalencia combinatoria entre grafos dirigidos y grafos bipartitos balanceados [1] [2] .

Propiedades

La doble cubierta bipartita de cualquier gráfico G es un gráfico bipartito . Ambas partes de un gráfico bipartito tienen un vértice para cada vértice de G. Una doble cubierta bipartita es conexa si y solo si G es conexa y no bipartita [3] .

La doble cobertura bipartita es un caso especial de cobertura bipartita ( gráfico de cobertura doble) . La doble cobertura en la teoría de grafos se puede considerar como un caso especial de doble cobertura topológica .

Si el gráfico G no es un gráfico simétrico bipartito , la cubierta bipartita de G también es un gráfico simétrico. De esta forma se pueden obtener algunos gráficos simétricos cúbicos muy conocidos . Por ejemplo, la cubierta bipartita de K 4 es un gráfico de cubo. La doble cubierta del gráfico de Petersen es el gráfico de Desargues, y la doble cubierta del dodecaedro es el gráfico cúbico simétrico de 40 vértices [4] .

Dos gráficos diferentes pueden tener cubiertas dobles bipartitas isomórficas . Por ejemplo, el grafo de Desargues no es solo una doble cubierta bipartita del grafo de Petersen, sino también una doble cubierta bipartita de otro grafo que no es isomorfo al grafo de Petersen [5] . No todo gráfico bipartito es una doble cubierta bipartita de otro gráfico. Para que un grafo bipartito G sea una cubierta bipartita de otro grafo, es necesario y suficiente que los automorfismos del grafo G incluyan una involución que mapee cada vértice a otro vértice no adyacente [5] . Por ejemplo, un gráfico con dos vértices y una arista es bipartito, pero no una doble cubierta bipartita, porque no contiene pares de vértices no adyacentes que puedan relacionarse entre sí mediante tal involución. Por otro lado, el gráfico del cubo es una doble cubierta bipartita y tiene una involución que asigna cada vértice a un vértice diametralmente opuesto. Sampatkumar [6] obtuvo una descripción alternativa de gráficos bipartitos que se pueden formar mediante la construcción de una cubierta doble bipartita .

Otras portadas dobles

En general, un gráfico puede tener varias cubiertas dobles además de una cubierta doble bipartita [7] . En la figura, el gráfico C es una doble cubierta del gráfico H :

  1. El gráfico C es un gráfico que cubre el gráfico H : hay un isomorfismo local sobreyectivo f de C a H , que se muestra en colores en la figura. Por ejemplo, f asigna ambos vértices azules de C al vértice azul en H . Además, sea X la vecindad del vértice azul en C y sea Y la vecindad del vértice azul en H . Entonces la restricción de f a X es una biyección de X a Y. En particular, los grados de cada uno de los vértices azules son iguales. Lo mismo se aplica a cualquier color.
  2. El gráfico C es una doble cubierta (o doble cubierta ) de H : la imagen inversa de cada vértice en H tiene un tamaño de 2. Por ejemplo, hay exactamente 2 vértices en C que corresponden al vértice azul en H.

Sin embargo, C no es una doble cubierta bipartita de H o cualquier otro gráfico. El gráfico no es un gráfico bipartito.

Si reemplazamos un triángulo con un cuadrado en H , el gráfico resultante tiene cuatro cubiertas dobles diferentes. Dos de ellos son bipartitos, pero solo uno de ellos es una cobertura de Kronecker.

Como otro ejemplo, el gráfico de icosaedro es una doble cubierta del gráfico completo K 6 . Para obtener un mapeo de cobertura del gráfico del icosaedro a K 6 , mapee cada par de vértices opuestos del icosaedro a un vértice de K 6 . Sin embargo, el icosaedro no es bipartito, por lo que el gráfico del icosaedro no es una doble cubierta bipartita del gráfico K 6 . En cambio, se puede obtener una doble cubierta bipartita como una doble cubierta orientable de la incrustación del grafo K 6 en el plano proyectivo .

Notas

  1. ↑ Dulmage, Mendelsohn, 1958 .
  2. ↑ Brualdi, Harary, Miller, 1980 .
  3. ↑ Brualdi, Harary, Miller, 1980 , pág. Teorema 3.4.
  4. ↑ Feng, Kutnar, Malnič, Marušic, 2008 .
  5. ↑ 12 Imrich , Pisanski, 2008 .
  6. ↑ Sampathkumar, 1975 .
  7. ↑ Waller, 1976 .

Literatura

Enlaces