Biregular graph

☆ Save On Wikipedia ↗
Graph families defined by their automorphisms
distance-transitive → distance-regular ← strongly regular
↓
symmetric (arc-transitive) ← t-transitive, t ≥ 2 skew-symmetric
↓
(if connected)
vertex- and edge-transitive		 → edge-transitive and regular → edge-transitive
↓ ↓ ↓
vertex-transitive → regular → (if bipartite)
biregular
↑
Cayley graph ← zero-symmetric asymmetric

In graph-theoretic mathematics, a biregular graph[1] or semiregular bipartite graph[2] is a bipartite graph G = ( U , V , E ) {\displaystyle G=(U,V,E)} {\displaystyle G=(U,V,E)} for which every two vertices on the same side of the given bipartition have the same degree as each other. If the degree of the vertices in U {\displaystyle U} {\displaystyle U} is x {\displaystyle x} {\displaystyle x} and the degree of the vertices in V {\displaystyle V} {\displaystyle V} is y {\displaystyle y} {\displaystyle y}, then the graph is said to be ( x , y ) {\displaystyle (x,y)} {\displaystyle (x,y)}-biregular.

The graph of the rhombic dodecahedron is biregular.

Example

Every complete bipartite graph K a , b {\displaystyle K_{a,b}} {\displaystyle K_{a,b}} is ( b , a ) {\displaystyle (b,a)} {\displaystyle (b,a)}-biregular.[3] The rhombic dodecahedron is another example; it is (3,4)-biregular.[4]

Vertex counts

An ( x , y ) {\displaystyle (x,y)} {\displaystyle (x,y)}-biregular graph G = ( U , V , E ) {\displaystyle G=(U,V,E)} {\displaystyle G=(U,V,E)} must satisfy the equation x | U | = y | V | {\displaystyle x|U|=y|V|} {\displaystyle x|U|=y|V|}. This follows from a simple double counting argument: the number of endpoints of edges in U {\displaystyle U} {\displaystyle U} is x | U | {\displaystyle x|U|} {\displaystyle x|U|}, the number of endpoints of edges in V {\displaystyle V} {\displaystyle V} is y | V | {\displaystyle y|V|} {\displaystyle y|V|}, and each edge contributes the same amount (one) to both numbers.

Symmetry

Every regular bipartite graph is also biregular. Every edge-transitive graph (disallowing graphs with isolated vertices) that is not also vertex-transitive must be biregular.[3] In particular every edge-transitive graph is either regular or biregular.

Configurations

The Levi graphs of geometric configurations are biregular; a biregular graph is the Levi graph of an (abstract) configuration if and only if its girth is at least six.[5]

References

  1. Scheinerman, Edward R.; Ullman, Daniel H. (1997), Fractional graph theory, Wiley-Interscience Series in Discrete Mathematics and Optimization, New York: John Wiley & Sons Inc., p. 137, ISBN 0-471-17864-0, MR 1481157.
  2. Dehmer, Matthias; Emmert-Streib, Frank (2009), Analysis of Complex Networks: From Biology to Linguistics, John Wiley & Sons, p. 149, ISBN 9783527627998.
  3. Lauri, Josef; Scapellato, Raffaele (2003), Topics in Graph Automorphisms and Reconstruction, London Mathematical Society Student Texts, Cambridge University Press, pp. 20–21, ISBN 9780521529037.
  4. Réti, Tamás (2012), "On the relationships between the first and second Zagreb indices" (PDF), MATCH Commun. Math. Comput. Chem., 68: 169–188, archived from the original (PDF) on 2017-08-29, retrieved 2012-09-02.
  5. Gropp, Harald (2007), "VI.7 Configurations", in Colbourn, Charles J.; Dinitz, Jeffrey H. (eds.), Handbook of combinatorial designs, Discrete Mathematics and its Applications (Boca Raton) (Second ed.), Chapman & Hall/CRC, Boca Raton, Florida, pp. 353–355.