Matrices and $α$-Stable Bipartite Graphs

Details Matrices and $α$-Stable Bipartite Graphs Matrices and $α$-Stable Bipartite Graphs

1999-12-15

arxiv.org/abs/math/9912120v1

Mathematics

Combinatorics

A preliminary version of this paper has been presented at the Tenth Haifa Matrix Theory Conference, January 1998, Technion, Ha

Scientific paper

A square (0,1)-matrix X of order n > 0 is called fully indecomposable if there exists no integer k with 0 < k < n, such that X has a k by n-k zero submatrix. A stable set of a graph G is a subset of pairwise nonadjacent vertices. The stability number of G, denoted by $\alpha (G)$, is the cardinality of a maximum stable set in G. A graph is called $\alpha $-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 $\alpha $-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, Marcus and Minc, Dulmage and Mendelsohn, and some generalizations of these statements. Several new results on $\alpha $-stable bipartite graphs and their corresponding reduced adjacency matrices are presented, as well. 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 strengthening of one Lewin's theorem claiming that the product of two fully indecomposable matrices is a fully indecomposable matrix.

Affiliated with

Also associated with

No associations

Rating

Matrices and $α$-Stable Bipartite Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Matrices and $α$-Stable Bipartite Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Matrices and $α$-Stable Bipartite Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-363793