Strongly connected multivariate digraphs
type: Item
instance of: scholarly article
title: Strongly connected multivariate digraphs
zbMATH Open document ID: 1358.05128
author: Yaokun Wu
author: Zeying Xu
author: Yinfeng Zhu
published in: The Electronic Journal of Combinatorics
publication date: 2017-04-10T00:00:00Z
full work available at URL: v24i1p47
review text: Summary: Generalizing the idea of viewing a digraph as a model of a linear map, we suggest a multi-variable analogue of a digraph, called a hydra, as a model of a multi-linear map. Walks in digraphs correspond to usual matrix multiplication while walks in hydras correspond to the tensor multiplication introduced by \textit{R. Grone} [J. Algebra 109, 14--24 (1987; Zbl 0653.15011)]. By viewing matrix multiplication as a special case of this tensor multiplication, many concepts on strongly connected digraphs are generalized to corresponding ones for hydras, including strongly connectedness, periods and primitiveness, etc. We explore the structure of all possible periods of strongly connected hydras, which turns out to be related to the existence of certain kind of combinatorial designs. We also provide estimates of largest primitive exponents and largest diameters of relevant hydras. Much existing research on tensors are based on some other definitions of multiplications of tensors and so our work here supplies new perspectives for understanding irreducible and primitive nonnegative tensors.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 6703739
zbMATH Keywords: de Bruijn form
zbMATH Keywords: cyclic decomposition
zbMATH Keywords: diameter
zbMATH Keywords: Markov operator
zbMATH Keywords: period
zbMATH Keywords: phase space
zbMATH Keywords: primitive exponent
zbMATH Keywords: hydra
zbMATH Keywords: tensor multiplication
MaRDI profile type: Publication
cites work: On the complexity of strongly connected components in directed hypergraphs
cites work: Q4304869
cites work: Diameter of orientations of graphs with given minimum degree
cites work: Q3993087
cites work: Algebraic Potential Theory on Graphs
cites work: Digraphs
cites work: Q5422499
cites work: Q3726125
cites work: Combinatorial matrix theory
cites work: Integer Programming and Combinatorial Optimization
cites work: Primitive tensors and directed hypergraphs
cites work: Q3426489
cites work: Perron-Frobenius theorem for nonnegative tensors
cites work: Primitivity, the Convergence of the NQZ Method, and the Largest Eigenvalue for Nonnegative Tensors
cites work: Distances in orientations of graphs
cites work: De Bruijn digraphs and affine transformations
cites work: General Theory of Natural Equivalences
cites work: Q3188930
cites work: Directed hypergraphs and applications
cites work: Normal Recurring Decimals
cites work: Markov chains and tensor multiplications
cites work: Q5675745
cites work: Positive dynamical systems in discrete time. Theory, models and applications
cites work: Q4094202
cites work: Q3096060
cites work: Basic Category Theory
cites work: An Introduction to Symbolic Dynamics and Coding
cites work: Q5704414
cites work: Q4681774
cites work: A Theorem on Graphs, with an Application to a Problem of Traffic Control
cites work: Q4595398
cites work: Wielandt's proof of the exponent inequality for primitive nonnegative matrices
cites work: Max algebraic powers of irreducible matrices in the periodic regime: an application of cyclic classes
cites work: A general product of tensors with applications
cites work: Tensors and Their Eigenvectors
cites work: Q3164470
cites work: On the discovery of the cycle-axiom of hypergraphs
cites work: Hoffman polynomials of nonnegative irreducible matrices and strongly connected digraphs
cites work: Tensor compositions and lists of combinatorial structures
cites work: An expansion property of Boolean linear maps
cites work: Lifespan in a primitive Boolean linear dynamical system
cites work: A conjecture on the primitive degree of tensors
cites work: Further results and some open problems on the primitive degree of nonnegative tensors
description: scientific article; zbMATH DE number 6703739