En matemáticas de teoría de grafos , un gráfico birregular [1] o un gráfico bipartito semirregular [2] es un gráfico bipartito para el cual cada dos 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 es y el grado de los vértices en es , entonces se dice que la gráfica es -birregular.
Familias de gráficos definidas por sus automorfismos | ||||
---|---|---|---|---|
distancia-transitiva | → | distancia regular | ← | muy regular |
↓ | ||||
simétrico (arco-transitivo) | ← | t -transitivo, t ≥ 2 | simétrico sesgado | |
↓ | ||||
(si está conectado) vértice y borde transitivo | → | edge-transititive y regular | → | borde transitivo |
↓ | ↓ | ↓ | ||
vértice-transitivo | → | regular | → | (si es bipartito) birregular |
↑ | ||||
Gráfico de Cayley | ← | simétrico cero | asimétrico |
Ejemplo
Cada gráfico bipartito completo es -birregular. [3] El dodecaedro rómbico es otro ejemplo; es (3,4) -birregular. [4]
Conteo de vértices
Un -Gráfico birregular debe satisfacer la ecuación . Esto se sigue de un simple argumento de recuento doble : el número de extremos de los bordes en es , el número de extremos de las aristas en es , y cada borde aporta la misma cantidad (uno) a ambos números.
Simetría
Cada gráfico bipartito regular también es birregular. Cada grafo de borde transitivo (que no permite grafos con vértices aislados ) que no sea también vértice transitivo debe ser birregular. [3] En particular, cada gráfico de borde transitivo 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 de al menos seis. [5]
Referencias
- ^ Scheinerman, Edward R .; Ullman, Daniel H. (1997), Teoría de grafos fraccionarios , Serie Wiley-Interscience en Matemáticas discretas y optimización, Nueva York: John Wiley & Sons Inc., p. 137, ISBN 0-471-17864-0, Señor 1481157.
- ^ Dehmer, Matthias; Emmert-Streib, Frank (2009), Análisis de redes complejas: de la biología a la lingüística , John Wiley & Sons, p. 149, ISBN 9783527627998.
- ^ a b Lauri, Josef; Scapellato, Raffaele (2003), Temas de Automorfismos Gráficos y Reconstrucción , Textos de Estudiantes de la Sociedad Matemática de Londres, Cambridge University Press, págs. 20–21, ISBN 9780521529037.
- ^ Réti, Tamás (2012), "Sobre las relaciones entre el primer y el segundo índice de Zagreb" (PDF) , MATCH Commun. Matemáticas. Computación. Chem. , 68 : 169-188, Archivado desde el original (PDF) en 29/08/2017 , obtenidos 2012-09-02.
- ^ Gropp, Harald (2007), "VI.7 Configurations", 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..