Linear operators that strongly preserve graphical properties of matrices

✍ Scribed by LeRoy B. Beasley; Norman J. Pullman

• Publisher: Elsevier Science
• Year: 1992
• Tongue: English
• Weight: 998 KB
• Volume: 104
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(92)90329-e

✦ Synopsis

Beasley, L.B. and N.J. Pullman, Linear operators that strongly preserve graphical properties of matrices, Discrete Mathematics 104 (1992) 143-157.

An operator on the set Ju of n X n matrices strongly preserves a subset 9 if it maps 9 into 9 and A% into A%. The operator semigroup of 9 is the semigroup of linear operators strongly preserving 9. We show that all the n x n matrix-families which are determined by the directed graphs of their members and satisfy a short list of conditions, have the same operator semigroup 2, and we determine the generators of Z. Among those matrix-families are: the irreducible matrices; the matrices whose directed graphs have maximum cycle length I > k for fixed k 3 4; and the matrices whose directed graphs have a path of length at least 12 k for fixed k * 3. Similar results are obtained for matrix-families determined by the undirected graphs of their members.