En matemáticas , un bigrafo es un conjunto de ternas desordenadas elegidas de un conjunto finito de vértices X , de modo que cada cuádruple desordenado de X contiene un número par de ternas del bigrafo. Un bigrafo regular tiene la propiedad de que cada par de vértices se encuentra en el mismo número de ternas del bigrafo. Los bigrafos se han estudiado debido a su conexión con líneas equiangulares y, para los bigrafos regulares, grafos fuertemente regulares y también grupos finitos porque muchos bigrafos regulares tienen grupos de automorfismos interesantes .
Un grafo de dos no es un grafo y no debe confundirse con otros objetos llamados grafos de dos en la teoría de grafos , como los grafos regulares de dos .
En el conjunto de vértices {1,...,6} la siguiente colección de triples desordenados es un dos-grafo:
Este bigrafo es un bigrafo regular ya que cada par de vértices distintos aparece junto en exactamente dos tripletas.
Dado un grafo simple G = ( V , E ), el conjunto de tripletas del conjunto de vértices V cuyo subgrafo inducido tiene un número impar de aristas forma un dos-grafo en el conjunto V . Todo dos-grafo puede representarse de esta manera. [1] Este ejemplo se conoce como la construcción estándar de un dos-grafo a partir de un grafo simple.
Como ejemplo más complejo, sea T un árbol con un conjunto de aristas E . El conjunto de todos los triples de E que no están contenidos en un camino de T forman un dos-grafo en el conjunto E . [2]
Un gráfico de dos es equivalente a una clase de conmutación de gráficos y también a una clase de conmutación (con signo) de gráficos completos con signo .
Cambiar un conjunto de vértices en un grafo (simple) significa invertir las adyacencias de cada par de vértices, uno en el conjunto y el otro no en el conjunto: así, el conjunto de aristas se cambia de modo que un par adyacente se vuelve no adyacente y un par no adyacente se vuelve adyacente. Las aristas cuyos puntos finales están ambos en el conjunto, o ambos no en el conjunto, no se cambian. Los grafos son equivalentes por conmutación si uno puede obtenerse del otro mediante conmutación. Una clase de equivalencia de grafos bajo conmutación se llama clase de conmutación . La conmutación fue introducida por van Lint y Seidel (1966) y desarrollada por Seidel; se ha llamado conmutación de grafos o conmutación de Seidel , en parte para distinguirla de la conmutación de grafos con signo .
En la construcción estándar de un dos-grafo a partir de un grafo simple dado anteriormente, dos grafos producirán el mismo dos-grafo si y solo si son equivalentes bajo conmutación, es decir, están en la misma clase de conmutación.
Sea Γ un dos-grafo en el conjunto X . Para cualquier elemento x de X , defina un grafo con el conjunto de vértices X que tenga vértices y y z adyacentes si y solo si { x , y , z } está en Γ. En este grafo, x será un vértice aislado. Esta construcción es reversible; dado un grafo simple G , adjunte un nuevo elemento x al conjunto de vértices de G , reteniendo el mismo conjunto de aristas, y aplique la construcción estándar anterior. Este dos-grafo se llama la extensión de G por x en el lenguaje de la teoría del diseño . [3] En una clase de conmutación dada de grafos de un dos-grafo regular, sea Γ x el único grafo que tiene x como vértice aislado (esto siempre existe, solo tome cualquier grafo en la clase y cambie el vecindario abierto de x ) sin el vértice x . Es decir, el dos-grafo es la extensión de Γ x por x . En el primer ejemplo anterior de un gráfico regular de dos, Γ x es un ciclo de 5 para cualquier elección de x . [4]
A un grafo G le corresponde un grafo completo con signo Σ sobre el mismo conjunto de vértices, cuyas aristas son negativas con signo si están en G y positivas si no están en G. A la inversa, G es el subgrafo de Σ que consta de todos los vértices y todas las aristas negativas. El bigrafo de G también puede definirse como el conjunto de tripletas de vértices que soportan un triángulo negativo (un triángulo con un número impar de aristas negativas) en Σ. Dos grafos completos con signo dan lugar al mismo bigrafo si y solo si son equivalentes bajo conmutación.
La conmutación de G y de Σ están relacionadas: intercambiar los mismos vértices en ambos produce un grafo H y su correspondiente grafo completo con signo.
La matriz de adyacencia de un grafo de dos es la matriz de adyacencia del grafo completo con signo correspondiente; por lo tanto, es simétrica , es cero en la diagonal y tiene entradas ±1 fuera de la diagonal. Si G es el grafo correspondiente al grafo completo con signo Σ, esta matriz se denomina matriz de adyacencia (0, −1, 1) o matriz de adyacencia de Seidel de G. La matriz de Seidel tiene cero entradas en la diagonal principal, -1 entradas para vértices adyacentes y +1 entradas para vértices no adyacentes.
Si los grafos G y H están en una misma clase de conmutación, los multiconjuntos de valores propios de las dos matrices de adyacencia de Seidel de G y H coinciden, ya que las matrices son similares. [5]
Un dos-grafo en un conjunto V es regular si y solo si su matriz de adyacencia tiene solo dos valores propios distintos ρ 1 > 0 > ρ 2, digamos, donde ρ 1 ρ 2 = 1 - | V |. [6]
Cada dos-grafo es equivalente a un conjunto de líneas en algún espacio euclidiano dimensional , cada par de las cuales se encuentran en el mismo ángulo. El conjunto de líneas construido a partir de un dos-grafo en n vértices se obtiene de la siguiente manera. Sea -ρ el valor propio más pequeño de la matriz de adyacencia de Seidel , A , del dos-grafo, y supongamos que tiene multiplicidad n - d . Entonces la matriz ρ I + A es semidefinida positiva de rango d y, por lo tanto, puede representarse como la matriz de Gram de los productos internos de n vectores en el d -espacio euclidiano. Como estos vectores tienen la misma norma (a saber, ) y productos internos mutuos ±1, cualquier par de las n líneas generadas por ellos se encuentran en el mismo ángulo φ donde cos φ = 1/ρ. A la inversa, cualquier conjunto de líneas equiangulares no ortogonales en un espacio euclidiano puede dar lugar a un dos-grafo (ver líneas equiangulares para la construcción). [7]
Con la notación anterior, la cardinalidad máxima n satisface n ≤ d (ρ 2 - 1)/(ρ 2 - d ) y el límite se alcanza si y solo si el bigrafo es regular.
Los dos-grafos en X que consisten en todos los triples posibles de X y ningún triple de X son dos-grafos regulares y se consideran dos-grafos triviales .
Para dos-grafos no triviales en el conjunto X , el dos-grafo es regular si y solo si para algún x en X el grafo Γ x es un grafo fuertemente regular con k = 2μ (el grado de cualquier vértice es el doble del número de vértices adyacentes a ambos de cualquier par de vértices no adyacentes). Si esta condición se cumple para un x en X , se cumple para todos los elementos de X . [8]
De ello se deduce que un grafo regular no trivial tiene un número par de puntos.
Si G es un grafo regular cuya extensión de dos grafos es Γ que tiene n puntos, entonces Γ es un dos grafo regular si y solo si G es un grafo fuertemente regular con valores propios k , r y s que satisfacen n = 2( k - r ) o n = 2( k - s ). [9]
