On the matrix sequence \(\{\Gamma(A^m)\}_{m=1}^\infty\) for a Boolean matrix \(A\) whose digraph is linearly connected. (English) Zbl 1286.05055
Summary: In this paper, we extend the results given by W. Park et al. [ibid. 438, No. 5, 2306–2319 (2013; Zbl 1258.05015)] by studying the convergence of the matrix sequence \(\{\Gamma(A^m)\}_{m=1}^\infty\) for a matrix \(A\in \mathcal B_n\) the digraph of which is linearly connected with an arbitrary number of strong components. In the process for generalization, we concretize ideas behind their arguments. We completely characterize \(A\) for which \(\{\Gamma(A^m)\}_{m=1}^\infty\) converges. Then we find its limit when all of the irreducible diagonal blocks are of order at least two. We go further to characterize \(A\) for which the limit of \(\{\Gamma(A^m)\}_{m=1}^\infty\) is a \(J\) block diagonal matrix. All of these results are derived by studying the \(m\)-step competition graph of the digraph of \(A\).
MSC:
| 05C20 | Directed graphs (digraphs), tournaments |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05B20 | Combinatorial aspects of matrices (incidence, Hadamard, etc.) |
| 15B34 | Boolean and Hadamard matrices |
Keywords:
irreducible Boolean \((0, 1)\)-matrices; powers of Boolean \((0, 1)\)-matrices; linearly connected digraphs; index of imprimitivity; \(m\)-step competition graphs; graph sequence; powers of digraphsCitations:
Zbl 1258.05015References:
| [1] | Brualdi, R. A.; Ryser, H. J., Combinatorial Matrix Theory (1991), Cambridge · Zbl 0746.05002 |
| [2] | Belmont, E., A complete characterization of paths that are \(m\)-step competition graphs, Discrete Appl. Math., 159, 1381-1390 (2011) · Zbl 1294.05082 |
| [3] | Cho, H. H.; Kim, H. K., Competition indices of strongly connected digraphs, Bull. Korean Math. Soc., 48, 637-646 (2011) · Zbl 1220.05047 |
| [4] | Cho, H. H.; Kim, S.-R.; Nam, Y., The \(m\)-step competition graph of a digraph, Discrete Appl. Math., 105, 115-127 (2000) · Zbl 0966.05066 |
| [6] | Greenberg, H. J.; Lundgren, J. R.; Maybee, J. S., Inverting graphs of rectangular matrices, Discrete Appl. Math., 8, 225-265 (1984) · Zbl 0545.05060 |
| [7] | Helleloid, G. T., Connected triangle-free \(m\)-step competition graphs, Discrete Appl. Math., 145, 376-383 (2005) · Zbl 1066.05120 |
| [8] | Kim, H. K., Competition indices of tournaments, Bull. Korean Math. Soc., 45, 385-396 (2008) · Zbl 1158.05027 |
| [9] | Ho, W., The \(m\)-step, same-step, and any-step competition graphs, Discrete Appl. Math., 152, 159-175 (2005) · Zbl 1080.05095 |
| [10] | Kim, S.-R., The competition number and its variants, (Gimbel, J.; Kennedy, J. W.; Quintas, L. V., Quo Vadis Graph Theory?. Quo Vadis Graph Theory?, Ann. Discrete Math., vol. 55 (1993)), 313-325 · Zbl 0789.05041 |
| [11] | Park, B.; Lee, J. Y.; Kim, S.-R., The \(m\)-step competition graphs of doubly partial orders, Appl. Math. Lett., 24, 811-816 (2011) · Zbl 1226.05127 |
| [12] | Park, W.; Park, B.; Kim, S.-R., A matrix sequence \(\{\Gamma(A^m) \}_{m = 1}^\infty\) might converge even if the matrix \(A\) is not primitive, Linear Algebra Appl., 438, 2306-2319 (2013) · Zbl 1258.05015 |
| [13] | Lundgren, J. R., Food webs, competition graphs, competition-common enemy graphs, and niche graphs, (Roberts, F. S., Applications of Combinatorics and Graph Theory in the Biological and Social Sciences. Applications of Combinatorics and Graph Theory in the Biological and Social Sciences, IMA Vol. Math. Appl., vol. 17 (1989), Springer-Verlag: Springer-Verlag New York), 221-243 · Zbl 0701.92023 |
| [14] | Raychaudhuri, A.; Roberts, F. S., Generalized competition graphs and their applications, Math. Methods Oper. Res., 49, 295-311 (1985) · Zbl 0572.05050 |
| [15] | Roberts, F. S., Competition graphs and phylogeny graphs, (Lovasz, L., Graph Theory and Combinatorial Biology. Graph Theory and Combinatorial Biology, Bolyai Soc. Math. Stud., vol. 7 (1999), J. Bolyai Math. Soc.: J. Bolyai Math. Soc. Budapest), 333-362 · Zbl 0924.05032 |
| [16] | Zhao, Y.; Chang, G. J., Note on the \(m\)-step competition numbers of paths and cycles, Discrete Appl. Math., 157, 1953-1958 (2009) · Zbl 1229.05189 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
