Grafo biregular

En matemáticas de teoría de grafos , un grafo biregular ^{[ 1 ]} o un grafo bipartito semirregular ^{[ 2 ]} es un grafo bipartito.${\displaystyle G=(U,V,E)}$para el cual cada par de vértices en el mismo lado de la bipartición dada tienen el mismo grado entre sí. Si el grado de los vértices en${\displaystyle U}$es${\displaystyle x}$y el grado de los vértices en${\displaystyle V}$es${\displaystyle y}$, entonces se dice que el gráfico es${\displaystyle (x,y)}$-biregular.

Cada grafo bipartito completo${\displaystyle K_{a,b}}$es${\displaystyle (b,a)}$-biregular. ^{[ 3 ]} El dodecaedro rómbico es otro ejemplo; es (3,4)-biregular. ^{[ 4 ]}

Un${\displaystyle (x,y)}$-grafo biregular${\displaystyle G=(U,V,E)}$debe satisfacer la ecuación${\displaystyle x|U|=y|V|}$. Esto se deduce de un simple argumento de doble conteo : el número de puntos finales de las aristas en${\displaystyle U}$es${\displaystyle x|U|}$, el número de puntos finales de las aristas en${\displaystyle V}$es${\displaystyle y|V|}$y cada arista contribuye con la misma cantidad (uno) a ambos números.

Todo grafo bipartito regular es también biregular. Todo grafo transitivo en aristas (excluyendo los grafos con vértices aislados ) que no sea transitivo en vértices debe ser biregular. ^{[ 3 ]} En particular, todo grafo transitivo en aristas es regular o biregular.

Los grafos de Levi de configuraciones geométricas son biregulares; un grafo biregular es el grafo de Levi de una configuración (abstracta) si y solo si su circunferencia es al menos seis. ^{[ 5 ]}