| Title:
|
Hall exponents of matrices, tournaments and their line digraphs (English) |
| Author:
|
Brualdi, Richard A. |
| Author:
|
Kiernan, Kathleen P. |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
61 |
| Issue:
|
2 |
| Year:
|
2011 |
| Pages:
|
461-481 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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). (English) |
| Keyword:
|
Hall matrix |
| Keyword:
|
Hall exponent |
| Keyword:
|
irreducible |
| Keyword:
|
primitive |
| Keyword:
|
tournament (matrix) |
| Keyword:
|
line digraph |
| MSC:
|
05C20 |
| MSC:
|
15A15 |
| MSC:
|
15B34 |
| idZBL:
|
Zbl 1249.15008 |
| idMR:
|
MR2905416 |
| DOI:
|
10.1007/s10587-011-0066-2 |
| . |
| Date available:
|
2011-06-06T10:35:09Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/141546 |
| . |
| Reference:
|
[1] Aigner, M.: On the line graph of a directed graph.Math. Z. 102 (1967), 56-61. MR 0216981, 10.1007/BF01110285 |
| Reference:
|
[2] Brualdi, R. A., Kiernan, K. P.: Landau's and Rado's theorems and partial tournaments.Electron. J. Comb. 16 (2009). Zbl 1159.05014, MR 2475542 |
| Reference:
|
[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. Zbl 0553.05039, MR 0776798 |
| Reference:
|
[4] Brualdi, R. A., Liu, B.: Hall exponents of Boolean matrices.Czechoslovak Math. J. 40(115) (1990), 659-670. Zbl 0737.05028, MR 1084901 |
| Reference:
|
[5] Brualdi, R. A., Ryser, H. J.: Combinatorial Matrix Theory.Cambridge Univ. Press Cambridge (1991). Zbl 0746.05002, MR 1130611 |
| Reference:
|
[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 |
| Reference:
|
[7] Huang, Y., Liu, B.: On a conjecture for fully indecomposable exponent and Hall exponent.Linear Multilinear Algebra 58 (2010), 699-710. Zbl 1201.15014, MR 2722753, 10.1080/03081080902843554 |
| Reference:
|
[8] Liu, B., Zhou, Bo: Estimates on strict Hall exponents.Australas. J. Comb. 19 (1999), 129-135. MR 1695868 |
| Reference:
|
[9] Liu, B., Zhou, Bo: On the Hall exponents of Boolean matrices.Linear Multilinear Algebra 46 (1999), 165-175. MR 1708586, 10.1080/03081089908818611 |
| Reference:
|
[10] Moon, J. W., Pullman, N. J.: On the powers of tournament matrices.J. Comb. Theory 3 (1967), 1-9. Zbl 0166.00901, MR 0213264, 10.1016/S0021-9800(67)80009-7 |
| Reference:
|
[11] Schwarz, Š.: The semigroup of fully indecomposable relations and Hall relations.Czechoslovak Math. J. 23(98) (1973), 151-163. Zbl 0261.20057, MR 0316612 |
| Reference:
|
[12] Tan, S., Liu, B., Zhang, D.: Extreme tournaments with given primitive exponents.Australas. J. Comb. 28 (2003), 81-91. MR 1998863 |
| . |
