# generateBipartiteGraphs -- generates the bipartite graphs with a given bipartition

## Synopsis

• Usage:
G = generateBipartiteGraphs n
G = generateBipartiteGraphs(n, m)
G = generateBipartiteGraphs(n, m, e)
G = generateBipartiteGraphs(n, m, le, ue)
G = generateBipartiteGraphs R
G = generateBipartiteGraphs(R, m)
G = generateBipartiteGraphs(R, m, e)
G = generateBipartiteGraphs(R, m, le, ue)
• Inputs:
• R, , the ring in which the graphs will be created
• n, an integer, the number of vertices of the graphs, must be positive (see caveat)
• m, an integer, the number of vertices in the first class of the bipartition
• e, an integer, the number of edges in the graphs
• le, an integer, a lower bound on the number of edges in the graphs
• ue, an integer, an upper bound on the number of edges in the graphs
• Optional inputs:
• Class2Degree2 => , default value false, whether the vertices in the second class must have at least two neighbors of degree at least 2
• Class2DistinctNeighborhoods => , default value false, whether all vertices in the second class must have distinct neighborhoods
• Class2MaxCommonNeighbors => an integer, default value null, an upper bound on the number of common neighbors of vertices in the second class
• MaxDegree => an integer, default value null, an upper bound on the degrees of the vertices
• MinDegree => an integer, default value null, a lower bound on the degrees of the vertices
• OnlyConnected => , default value false, whether to only allow connected graphs
• Outputs:
• G, a list, the bipartite graphs satisfying the input conditions

## Description

This method generates all bipartite graphs on $n$ vertices. The size of the bipartition is specified by giving the size of one class; the other class is determined automatically from the number of vertices.

If only one integer argument is given, then the method generates all bipartite graphs on that number of vertices with first class of sizes $0$ to $n$.

If a PolynomialRing $R$ is supplied instead, then the number of vertices is the number of generators. Moreover, the strings are automatically converted to graphs in $R$.

 i1 : R = QQ[a..e]; i2 : generateBipartiteGraphs(R, 2) o2 = {Graph{edges => {} }, Graph{edges => {{a, e}} }, ring => R ring => R vertices => {a, b, c, d, e} vertices => {a, b, c, d, e} ------------------------------------------------------------------------ Graph{edges => {{a, e}, {b, e}} }, Graph{edges => {{a, d}, {a, e}} }, ring => R ring => R vertices => {a, b, c, d, e} vertices => {a, b, c, d, e} ------------------------------------------------------------------------ Graph{edges => {{a, d}, {b, e}} }, Graph{edges => {{a, d}, {a, e}, {b, ring => R ring => R vertices => {a, b, c, d, e} vertices => {a, b, c, d, e} ------------------------------------------------------------------------ e}}}, Graph{edges => {{a, d}, {b, d}, {a, e}, {b, e}}}, ring => R vertices => {a, b, c, d, e} ------------------------------------------------------------------------ Graph{edges => {{a, c}, {a, d}, {a, e}}}, Graph{edges => {{a, c}, {a, ring => R ring => R vertices => {a, b, c, d, e} vertices => {a, b, c, ------------------------------------------------------------------------ d}, {a, e}, {b, e}}}, Graph{edges => {{a, c}, {b, d}, {a, e}}}, ring => R d, e} vertices => {a, b, c, d, e} ------------------------------------------------------------------------ Graph{edges => {{a, c}, {b, d}, {a, e}, {b, e}}}, ring => R vertices => {a, b, c, d, e} ------------------------------------------------------------------------ Graph{edges => {{a, c}, {a, d}, {b, d}, {a, e}, {b, e}}}, ring => R vertices => {a, b, c, d, e} ------------------------------------------------------------------------ Graph{edges => {{a, c}, {b, c}, {a, d}, {b, d}, {a, e}, {b, e}}}} ring => R vertices => {a, b, c, d, e} o2 : List

## Caveat

The number of vertices $n$ must be positive as nauty cannot handle graphs with zero vertices.

• generateGraphs -- generates the graphs on a given number of vertices

## Ways to use generateBipartiteGraphs :

• "generateBipartiteGraphs(PolynomialRing)"
• "generateBipartiteGraphs(PolynomialRing,ZZ)"
• "generateBipartiteGraphs(PolynomialRing,ZZ,ZZ)"
• "generateBipartiteGraphs(PolynomialRing,ZZ,ZZ,ZZ)"
• "generateBipartiteGraphs(ZZ)"
• "generateBipartiteGraphs(ZZ,ZZ)"
• "generateBipartiteGraphs(ZZ,ZZ,ZZ)"
• "generateBipartiteGraphs(ZZ,ZZ,ZZ,ZZ)"

## For the programmer

The object generateBipartiteGraphs is .