In
graph-theoretic mathematics, a biregular graph or semiregular bipartite graph is a
bipartite graph
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V a ...
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.
Example
Every
complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17.
Graph theory i ...
is
-biregular.
The
rhombic dodecahedron
In geometry, the rhombic dodecahedron is a convex polyhedron with 12 congruent rhombic faces. It has 24 edges, and 14 vertices of 2 types. It is a Catalan solid, and the dual polyhedron of the cuboctahedron.
Properties
The rhombic dodecahed ...
is another example; it is (3,4)-biregular.
Vertex counts
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
Every
regular bipartite graph is also biregular.
Every
edge-transitive graph
In the mathematical field of graph theory, an edge-transitive graph is a graph such that, given any two edges and of , there is an automorphism of that maps to .
In other words, a graph is edge-transitive if its automorphism group acts ...
(disallowing graphs with
isolated vertices) that is not also
vertex-transitive
In geometry, a polytope (e.g. a polygon or polyhedron) or a tiling is isogonal or vertex-transitive if all its vertices are equivalent under the symmetries of the figure. This implies that each vertex is surrounded by the same kinds of fa ...
must be biregular.
[.] In particular every edge-transitive graph is either regular or biregular.
Configurations
The
Levi graphs of
geometric configuration
In mathematics, specifically projective geometry, a configuration in the plane consists of a finite set of points, and a finite arrangement of lines, such that each point is incident to the same number of lines and each line is incident to the ...
s are biregular; a biregular graph is the Levi graph of an (abstract) configuration if and only if its
girth
Girth may refer to:
;Mathematics
* Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space
* Girth (geometry), the perimeter of a parallel projection of a shape
* Girth ...
is at least six.
[.]
References
{{reflist
Bipartite graphs