Premium
Graph‐theoretic characterization of the matrix property of full irreducibility without using a transversal
Author(s) -
Kevorkian Aram K.
Publication year - 1979
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190030207
Subject(s) - irreducibility , mathematics , transversal (combinatorics) , bipartite graph , combinatorics , line graph , discrete mathematics , matrix (chemical analysis) , graph , pure mathematics , mathematical analysis , materials science , composite material
In this paper we introduce the notion of strongly connected polygons in the line graph of a bipartite graph. We use this notion to give a necessary and sufficient condition for a matrix Y to be fully irreducible without the need to construct a transversal of Y. In addition, we show that the notion of strongly connected polygons forms the basis of a general theory that may be used for finding all the cycles in the directed graph of a fully irreducible matrix and for constructing all the nonzero transversals of a fully irreducible matrix.