
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_{1}, ..., a_{m}} ∪ {b_{1}, ..., 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_{i}b_{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 wellknown 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
