Canonical binary matrices related to bipartite graphs

Abstract

The current paper is dedicated to the problem of finding the number of mutually non isomorphic bipartite graphs of the type $g=⟨R_g,C_g,E_g⟩$ at given $n=|R_g|$ and $m=|C_g|$, where $R_g$ and $C_g$ are the two disjoint parts of the vertices of the graphs $g$, and $E_g$ is the set of edges, $Eg\subseteq R_g\times C_g$. For this purpose, the concept of canonical binary matrix is introduced. The different canonical matrices unambiguously describe the different with exactness up to isomorphism bipartite graphs. We have found a necessary and sufficient condition an arbitrary matrix to be canonical. This condition could be the base for realizing recursive algorithm for finding all $n\times m$ canonical binary matrices and consequently for finding all with exactness up to isomorphism binary matrices with cardinality of each part equal to $n$ and $m$.