Bipartite Graphs Related to Mutually Disjoint S-Permutation Matrices

Some numerical characteristics of bipartite graphs in relation to the problem of finding all disjoint pairs of S-permutation matrices in the general case are discussed in this paper. All bipartite graphs of the type , where or , are provided. The cardinality of the sets of mutually disjoint S-permutation matrices in both the and cases is calculated. 1. Introduction Let be a positive integer. By we denote the set We let denote the symmetric group of order , that is, the group of all one-to-one mappings of the set to itself. If , , then the image of the element in the mapping we will denote by . A bipartite graph is an ordered triple where and are nonempty sets such that . The elements of will be called vertices. The set of edges is . Multiple edges are not allowed in our considerations. The subject of the present work is bipartite graphs considered up to isomorphism. We refer to [1] or [2] for more details on graph theory. Let and be two nonnegative integers, and let . We denote by the set of all bipartite graphs of the type , considered up to isomorphism, such that and . Let , be square matrices, whose entries are elements of the set ？ . The matrix is called a Sudoku matrix, if every row, every column, and every submatrix , comprise a permutation of the elements of set , that is, every number is found just once in each row, column, and submatrix . Submatrices are called blocks of . Sudoku is a very popular game, and Sudoku matrices are special cases of Latin squares in the class of gerechte designs [3]. A matrix is called binary if all of its elements are equal to 0 or 1. A square binary matrix is called permutation matrix if in every row and every column there is just one 1. Let us denote by the set of all permutation matrices of the following type: where for every , is a square binary submatrix (block) with only one element equal to 1. The elements of will be called S-permutation matrices. Two matrices and , will be called disjoint if there are not elements and with the same indices such that . The concept of S-permutation matrix was introduced by Dahl [4] in relation to the popular Sudoku puzzle. Obviously, a square matrix with entries from is a Sudoku matrix if and only if there are matrices pairwise disjoint, such that can be written in the following way: In [5] Fontana offers an algorithm which returns a random family of mutually disjoint S-permutation matrices, where . For , he ran the algorithm 1000 times and found 105 different families of nine mutually disjoint S-permutation matrices. Then, applying (1.5), he decided that there are at least