For faster navigation, this Iframe is preloading the Wikiwand page for Biregular graph.

Biregular graph

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 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 is and the degree of the vertices in is , then the graph is said to be -biregular.

The graph of the rhombic dodecahedron is biregular.

Example

[edit]

Every complete bipartite graph is -biregular.[3] The rhombic dodecahedron is another example; it is (3,4)-biregular.[4]

Vertex counts

[edit]

An -biregular graph must satisfy the equation . This follows from a simple double counting argument: the number of endpoints of edges in is , the number of endpoints of edges in is , and each edge contributes the same amount (one) to both numbers.

Symmetry

[edit]

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

[edit]

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

[edit]
  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. ^ a b 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.
{{bottomLinkPreText}} {{bottomLinkText}}
Biregular graph
Listen to this article

This browser is not supported by Wikiwand :(
Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience.
Please download and use one of the following browsers:

This article was just edited, click to reload
This article has been deleted on Wikipedia (Why?)

Back to homepage

Please click Add in the dialog above
Please click Allow in the top-left corner,
then click Install Now in the dialog
Please click Open in the download dialog,
then click Install
Please click the "Downloads" icon in the Safari toolbar, open the first download in the list,
then click Install
{{::$root.activation.text}}

Install Wikiwand

Install on Chrome Install on Firefox
Don't forget to rate us

Tell your friends about Wikiwand!

Gmail Facebook Twitter Link

Enjoying Wikiwand?

Tell your friends and spread the love:
Share on Gmail Share on Facebook Share on Twitter Share on Buffer

Our magic isn't perfect

You can help our automatic cover photo selection by reporting an unsuitable photo.

This photo is visually disturbing This photo is not a good choice

Thank you for helping!


Your input will affect cover photo selection, along with input from other users.

X

Get ready for Wikiwand 2.0 🎉! the new version arrives on September 1st! Don't want to wait?