Gráfico birregular

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

La gráfica del dodecaedro rómbico es birregular.

Ejemplo

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

Recuento de vértices

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

Simetría

Todo grafo bipartito regular es también birregular. Todo grafo transitivo por aristas (sin admitir grafos con vértices aislados ) que no sea también transitivo por vértices debe ser birregular. ^[3] En particular, todo grafo transitivo por aristas es regular o birregular.

Configuraciones

Los gráficos de Levi de configuraciones geométricas son birregulares; un gráfico birregular es el gráfico de Levi de una configuración (abstracta) si y solo si su circunferencia es al menos seis. ^[5]

Referencias

1. Scheinerman, Edward R. ; Ullman, Daniel H. (1997), Teoría de grafos fraccionarios , Wiley-Interscience Series in Discrete Mathematics and Optimization, Nueva York: John Wiley & Sons Inc., pág. 137, ISBN 0-471-17864-0, Sr.  1481157.
2. Dehmer, Matthias; Emmert-Streib, Frank (2009), Análisis de redes complejas: de la biología a la lingüística, John Wiley & Sons, pág. 149, ISBN 9783527627998.
3. Lauri, Josef; Scapellato, Raffaele (2003), Temas de automorfismos y reconstrucción de grafos, Textos para estudiantes de la London Mathematical Society, Cambridge University Press, págs. 20-21, ISBN 9780521529037.
4. Réti, Tamás (2012), "Sobre las relaciones entre el primer y el segundo índice de Zagreb" (PDF) , MATCH Commun. Math. Comput. Chem. , 68 : 169–188, archivado desde el original (PDF) el 2017-08-29 , consultado el 2012-09-02.
5. Gropp, Harald (2007), "VI.7 Configuraciones", en Colbourn, Charles J.; Dinitz, Jeffrey H. (eds.), Manual de diseños combinatorios , Matemáticas discretas y sus aplicaciones (Boca Raton) (segunda ed.), Chapman & Hall/CRC, Boca Raton, Florida, págs. 353–355.