Mitad bipartita

En teoría de grafos , la mitad bipartita o el semicuadrado de un grafo bipartito G = ( U , V , E ) es un grafo cuyo conjunto de vértices es uno de los dos lados de la bipartición ( sin pérdida de generalidad , U ) y en el que hay una arista u _i u _j para cada par de vértices u _i , u _j en U que están a distancia dos entre sí en G . ^{[ 1 ]} Es decir, en una notación más compacta, la mitad bipartita es G ² [ U ] donde el superíndice 2 denota el cuadrado de un grafo y los corchetes denotan un subgrafo inducido .

Por ejemplo, la mitad bipartita del grafo bipartito completo K _{n , n} es el grafo completo K _n y la mitad bipartita del grafo hipercubo es el grafo cubo dividido por la mitad . Cuando G es un grafo distancia-regular , sus dos mitades bipartitas son ambas distancia-regulares. ^{[ 2 ]} Por ejemplo, el grafo Foster dividido por la mitad es uno de un número finito de grafos localmente lineales distancia -regulares de grado 6. ^{[ 3 ]}

Todo grafo G es la mitad bipartita de otro grafo, formada al subdividir las aristas de G en caminos de dos aristas. De forma más general, se puede encontrar una representación de G como mitad bipartita tomando cualquier cubierta de aristas de clique de G y reemplazando cada clique por una estrella . ^{[ 4 ]} Toda representación surge de esta manera. Dado que encontrar la cubierta de aristas de clique más pequeña es NP-difícil, también lo es encontrar el grafo con el menor número de vértices para el cual G es la mitad bipartita. ^{[ 5 ]}

Los grafos de mapas , es decir, los grafos de intersección de regiones simplemente conexas disjuntas interiormente en el plano, son exactamente las mitades bipartitas de grafos planares bipartitos . ^{[ 6 ]}

• Doble cubierta bipartita