Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
Hall matrix; Hall exponent; irreducible; primitive; tournament (matrix); line digraph
Hall matrix; Hall exponent; irreducible; primitive; tournament (matrix); line digraph
Summary:
Let $A$ be a square $(0,1)$-matrix. Then $A$ is a Hall matrix provided it has a nonzero permanent. The Hall exponent of $A$ is the smallest positive integer $k$, if such exists, such that $A^k$ is a Hall matrix. The Hall exponent has received considerable attention, and we both review and expand on some of its properties. Viewing $A$ as the adjacency matrix of a digraph, we prove several properties of the Hall exponents of line digraphs with some emphasis on line digraphs of tournament (matrices).
References:
[1] Aigner, M.: On the line graph of a directed graph. Math. Z. 102 (1967), 56-61. DOI 10.1007/BF01110285 | MR 0216981
[2] Brualdi, R. A., Kiernan, K. P.: Landau's and Rado's theorems and partial tournaments. Electron. J. Comb. 16 (2009). MR 2475542 | Zbl 1159.05014
[3] Brualdi, R. A., Li, Q.: The interchange graph of tournaments with the same score vector. In: Progress in Graph Theory (Waterloo, Ont. 1982) Academic Press Toronto, ON (1984), 129-151. MR 0776798 | Zbl 0553.05039
[4] Brualdi, R. A., Liu, B.: Hall exponents of Boolean matrices. Czechoslovak Math. J. 40(115) (1990), 659-670. MR 1084901 | Zbl 0737.05028
[5] Brualdi, R. A., Ryser, H. J.: Combinatorial Matrix Theory. Cambridge Univ. Press Cambridge (1991). MR 1130611 | Zbl 0746.05002
[6] Hemminger, R. L., Beineke, L. W.: Line graphs and line digraphs. Selected Topics in Graph Theory Academic Press, New York, 271-305 (1978). Zbl 0434.05056
[7] Huang, Y., Liu, B.: On a conjecture for fully indecomposable exponent and Hall exponent. Linear Multilinear Algebra 58 (2010), 699-710. DOI 10.1080/03081080902843554 | MR 2722753 | Zbl 1201.15014
[8] Liu, B., Zhou, Bo: Estimates on strict Hall exponents. Australas. J. Comb. 19 (1999), 129-135. MR 1695868
[9] Liu, B., Zhou, Bo: On the Hall exponents of Boolean matrices. Linear Multilinear Algebra 46 (1999), 165-175. DOI 10.1080/03081089908818611 | MR 1708586
[10] Moon, J. W., Pullman, N. J.: On the powers of tournament matrices. J. Comb. Theory 3 (1967), 1-9. DOI 10.1016/S0021-9800(67)80009-7 | MR 0213264 | Zbl 0166.00901
[11] Schwarz, Š.: The semigroup of fully indecomposable relations and Hall relations. Czechoslovak Math. J. 23(98) (1973), 151-163. MR 0316612 | Zbl 0261.20057
[12] Tan, S., Liu, B., Zhang, D.: Extreme tournaments with given primitive exponents. Australas. J. Comb. 28 (2003), 81-91. MR 1998863
Search
Partner of
