2017/05/04 by Abdullah Atmaca, Atmaca, Abdullah, A. Yavuz Oruç +1
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1705.01800
openalex publication_date 2017/05/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper solves a problem that was stated by M. A. Harrison in 1973~\citeharrison1973number. This problem, that has remained open since then is concerned with counting equivalence classes of n× r binary matrices under row and column permutations. Let I and O denote two sets of vertices, where I∩ O =Φ, |I| = n, |O| = r, and Bu(n,r) denote the set of unlabeled graphs whose edges connect vertices in I and O. Harrison established that the number of equivalence classes of n× r binary matrices is equal to the number of unlabeled graphs in Bu(n,r). He also computed the number of such matrices (hence such graphs) for small values of n and r without providing an asymptotic formula |Bu(n,r)|. Here, such an asymptotic formula is provided by proving the following two-sided equality using Polya's Counting Theorem.