Matrices and α-Stable Bipartite Graphs

Vadim E. Levit (Ariel University Center of Samaria, Israel)

Eugen Mandrescu (Holon Institute of Technology, Israel)

Abstract: A square (0, 1)-matrix X of order n ≥ 1 is called fully indecomposable if there exists no integer k with 1 ≤ k ≤ n - 1, such that X has a k by n - k zero submatrix. The reduced adjacency matrix of a bipartite graph G = (A, B, E) (having A ∪ B = {a₁, ..., a_m} ∪ {b₁, ..., b_n} as a vertex set, and E as an edge set), is X = [x_ij], 1 ≤ i ≤ m, 1 ≤ j ≤ n, where x_ij = 1 if a_ib_j ∈ E and x_ij = 0 otherwise. A stable set of a graph G is a subset of pairwise nonadjacent vertices. The stability number of G, denoted by α(G), is the cardinality of a maximum stable set in G. A graph is called α-stable if its stability number remains the same upon both the deletion and the addition of any edge. We show that a connected bipartite graph has exactly two maximum stable sets that partition its vertex set if and only if its reduced adjacency matrix is fully indecomposable. We also describe a decomposition structure of α-stable bipartite graphs in terms of their reduced adjacency matrices. On the base of these findings, we obtain both new proofs for a number of well-known theorems on the structure of matrices due to Brualdi (1966), Marcus and Minc (1963), Dulmage and Mendelsohn (1958), and some generalizations of these statements. Two kinds of matrix product are also considered (namely, Boolean product and Kronecker product), and their corresponding graph operations. As a consequence, we obtain a new proof of one Lewin's theorem claiming that the product of two fully indecomposable matrices is a fully indecomposable matrix.

Keywords: Boolean product, Kronecker product, adjacency matrix, bistable bipartite graph, cover irreducible matrix, elementary graph, fully indecomposable matrix, perfect matching, stable set, total support

Categories: G.2.1, G.2.2