Biregular graph

In graph-theoretic mathematics, a biregular graph{{citation

| last1 = Scheinerman | first1 = Edward R. | authorlink = Ed Scheinerman

| last2 = Ullman | first2 = Daniel H.

| isbn = 0-471-17864-0

| location = New York

| mr = 1481157

| page = 137

| publisher = John Wiley & Sons Inc.

| series = Wiley-Interscience Series in Discrete Mathematics and Optimization

| title = Fractional graph theory

| year = 1997}}. or semiregular bipartite graph{{citation

| last1 = Dehmer | first1 = Matthias

| last2 = Emmert-Streib | first2 = Frank

| isbn = 9783527627998

| page = 149

| publisher = John Wiley & Sons

| title = Analysis of Complex Networks: From Biology to Linguistics

| url = https://books.google.com/books?id=l9zURPH2GiUC&pg=PA149

| year = 2009}}. is a bipartite graph $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$ is $x$ and the degree of the vertices in $V$ is $y$ , then the graph is said to be $(x,y)$ -biregular.

File:Rhombicdodecahedron.jpg is biregular.]]

Example

Every complete bipartite graph $K_{a,b}$ is $(b,a)$ -biregular.

The rhombic dodecahedron is another example; it is (3,4)-biregular.{{citation

|last = Réti

|first = Tamás

|journal = MATCH Commun. Math. Comput. Chem.

|pages = 169–188

|title = On the relationships between the first and second Zagreb indices

|url = http://www.pmf.kg.ac.rs/match/electronic_versions/match68/n1/match68n1_169-188.pdf

|volume = 68

|year = 2012

|access-date = 2012-09-02

|archive-url = https://web.archive.org/web/20170829145123/http://www.pmf.kg.ac.rs/match/electronic_versions/match68/n1/match68n1_169-188.pdf

|archive-date = 2017-08-29

|url-status = dead

}}.

Vertex counts

An $(x,y)$ -biregular graph $G=(U,V,E)$ must satisfy the equation $x|U|=y|V|$ . This follows from a simple double counting argument: the number of endpoints of edges in $U$ is $x|U|$ , the number of endpoints of edges in $V$ is $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.{{citation

| last1 = Lauri | first1 = Josef

| last2 = Scapellato | first2 = Raffaele

| isbn = 9780521529037

| pages = 20–21

| publisher = Cambridge University Press

| series = London Mathematical Society Student Texts

| title = Topics in Graph Automorphisms and Reconstruction

| url = https://books.google.com/books?id=hsymFm0E0uIC&pg=PA20

| year = 2003}}. 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.{{citation

| last = Gropp | first = Harald

| editor1-last = Colbourn | editor1-first = Charles J.

| editor2-last = Dinitz | editor2-first = Jeffrey H.

| contribution = VI.7 Configurations

| edition = Second

| pages = 353–355

| publisher = Chapman & Hall/CRC, Boca Raton, Florida

| series = Discrete Mathematics and its Applications (Boca Raton)

| title = Handbook of combinatorial designs

| year = 2007}}.

References

Category:Bipartite graphs