×

zbMATH — the first resource for mathematics

Generalized primitivity of labeled digraphs. (English) Zbl 1379.05047
Drmota, Michael (ed.) et al., Extended abstracts of the ninth European conference on combinatorics, graph theory and applications, EuroComb 2017, Vienna, Austria, August 28 – September 1, 2017. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 61, 549-555 (2017).
Summary: We study reachability properties of digraphs whose edges are labeled by elements of a semigroup. We introduce a notion of primitivity for such digraphs, which allows us to unify a variety of recent results on the combinatorial structure of semigroups of nonnegative square matrices. We make use of Stallings foldings, a key procedure in combinatorial group theory, to design an almost-linear time algorithm for checking primitivity in an important case of allowable digraphs improving the previously known algorithm. We also present computational complexity results related to computation of the exponent.
For the entire collection see [Zbl 1375.05004].

MSC:
05C20 Directed graphs (digraphs), tournaments
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
PDF BibTeX Cite
Full Text: DOI
References:
[1] Al’pin, Y. A.; Al’pina, V. S., Combinatorial properties of irreducible semigroups of nonnegative matrices, J. Math. Sci., 191, 4-9, (2013) · Zbl 1276.15015
[2] Blondel, V. D.; Jungers, R. M.; Olshevsky, A., On primitivity of sets of matrices, Automatica, 61, 80-88, (2015) · Zbl 1337.15024
[3] Brualdi, R.; Ryser, H., Combinatorial matrix theory, (1991), Cambridge University Press · Zbl 0746.05002
[4] Clifford, A. H.; Preston, G. B., The algebraic theory of semigroups. vol. I, (1961), American Mathematical Society Providence, R.I. · Zbl 0111.03403
[5] Fornasini, E.; Valcher, M. E., Directed graphs, 2d state models, and characteristic polynomials of irreducible matrix pairs, Linear Algebra Appl., 263, 275-310, (1997) · Zbl 0887.93033
[6] Frobenius, G., Über matrizen aus nicht negativen elementen, I, Sitzungsber, Kgl. Preuss Akad. Wiss., 456-477, (1912) · JFM 43.0204.09
[7] Gerencsér, B.; Gusev, V. V.; Jungers, R. M., Primitive sets of nonnegative matrices and synchronizing automata, (2016), manuscript, preprint
[8] Meyer, C. D., Matrix analysis and applied linear algebra, (2000), Society for Industrial and Applied Mathematics Philadelphia, PA, USA
[9] Olesky, D.; Shader, B.; van den Driessche, P., Exponents of tuples of nonnegative matrices, Linear Algebra Appl., 356, 123-134, (2002) · Zbl 1018.15018
[10] Protasov, V. Y., Classification of k-primitive sets of matrices, SIAM Journal on Matrix Analysis and Applications, 34, 1174-1188, (2013) · Zbl 1281.15039
[11] Protasov, V. Y.; Voynov, A. S., Sets of nonnegative matrices without positive products, Linear Algebra Appl., 437, 749-765, (2012) · Zbl 1245.15033
[12] Romanovsky, M. V., Un théorème sur LES zéros des matrices non négatives, Bulletin de la S.M.F., 61, 213-219, (1933) · JFM 59.0112.02
[13] Touikan, N. W.M., A fast algorithm for stallings’ folding process, International Journal of Algebra and Computation, 16, 1031-1045, (2006) · Zbl 1111.20032
[14] Voynov, A. S.; Protasov, V. Y., Compact noncontraction semigroups of affine operators, Sbornik: Mathematics, 206, 921-940, (2015) · Zbl 1341.47048
[15] Wu, Y.; Zhu, Y., Lifespan in a primitive Boolean linear dynamical system, Electr. J. Comb., 22, (2015) · Zbl 1329.05203
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.