2016•arXiv (Cornell University)Open access

Canonical binary matrices related to bipartite graphs

Krasimir Yordzhev

Open full text 0 citations

Abstract

The current paper is dedicated to the problem of finding the number of mutually non isomorphic bipartite graphs of the type $g=\langle R_g ,C_g ,E_g \rangle$ 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$.

Open-access reader

About this research paper

What this paper is about

The current paper is dedicated to the problem of finding the number of mutually non isomorphic bipartite graphs of the type $g=\langle R_g ,C_g ,E_g \rangle$ 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$.

Why it matters

A significance statement is not available in the OpenAlex record.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

The current paper is dedicated to the problem of finding the number of mutually non isomorphic bipartite graphs of the type $g=\langle R_g ,C_g ,E_g \rangle$ 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$.

Key concepts: Bipartite graph, Combinatorics, Mathematics, Disjoint sets, Cardinality (data modeling), Binary number, Canonical form, Isomorphism (crystallography)

Related papers

Back to paper searchBrowse research topicsOriginal source
Canonical binary matrices related to bipartite graphs — Research Paper | ScholarLens