Which digraphs with ring structure are essentially cyclic?

DOI10.1016/J.AAM.2010.01.005MaRDI QIDQ984026zbMATH OpenOpenAlexFDO

Authors R. P. Agaev, Pavel Chebotarev

Publication date 13 July 2010

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0910.3113

zbMATH Keywords

Chebyshev polynomialDirected graphessential cyclicityLaplacian matrixLaplacian spectrumspanning treeweighted digraph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: We say that a digraph is essentially cyclic if its Laplacian spectrum is not completely real. The essential cyclicity implies the presence of directed cycles, but not vice versa. The problem of characterizing essential cyclicity in terms of graph topology is difficult and yet unsolved. Its solution is important for some applications of graph theory, including that in decentralized control. In the present paper, this problem is solved with respect to the class of digraphs with ring structure, which models some typical communication networks. It is shown that the digraphs in this class are essentially cyclic, except for certain specified digraphs. The main technical tool we employ is the Chebyshev polynomials of the second kind. A by-product of this study is a theorem on the zeros of polynomials that differ by one from the products of Chebyshev polynomials of the second kind. We also consider the problem of essential cyclicity for weighted digraphs and enumerate the spanning trees in some digraphs with ring structure.

Recommendations

• Ring structure digraphs: spectrum of adjacency matrix and application
• A class of digraphs which have completely real Laplacian spectra
• The Laplacian spectrum of some digraphs obtained from the wheel
• Circulant digraphs determined by their spectra
• Further results on digraphs with completely real Laplacian spectra

Cites work

• Algebraic connectivity of directed graphs
• Bounds for eigenvalues of doubly stochastic matrices
• Chebyshev polynomials and spanning tree formulas for circulant and related graphs
• Consensus and Cooperation in Networked Multi-Agent Systems
• Coordination in multiagent systems and Laplacian spectra of digraphs
• Distributed consensus in multi-vehicle cooperative control. Theory and applications.
• Eigenvalues of the Laplacian of a graph^∗
• Flocks and formations
• Forest matrices around the Laplacian matrix
• scientific article; zbMATH DE number 3658906 (Why is no real title available?)
• scientific article; zbMATH DE number 3717357 (Why is no real title available?)
• scientific article; zbMATH DE number 847580 (Why is no real title available?)
• scientific article; zbMATH DE number 3204642 (Why is no real title available?)
• Kernels of directed graph Laplacians
• Laplacians and the Cheeger inequality for directed graphs
• On $W$-bases of directed graphs
• On proximity measures for graph vertices
• On the spectra of nonsymmetric Laplacian matrices
• Parallel concepts in graph theory
• Spanning forests of a digraph and their applications
• Spanning tree formulas and Chebyshev polynomials
• The matrix of maximum out forests of a digraph and its applications
• The matrix-forest theorem and measuring relations in small social groups

Cited in

(10)

• Further results on digraphs with completely real Laplacian spectra
• A class of digraphs which have completely real Laplacian spectra
• Complex adjacency spectra of digraphs
• Tight bound on parameter of surplus-based averaging algorithm over balanced digraphs
• On singularity and properties of eigenvectors of complex Laplacian matrix of multidigraphs
• Scale fragilities in localized consensus dynamics
• Ring structure digraphs: spectrum of adjacency matrix and application
• Realizable cycle structures in digraphs
• Scalable second-order consensus of hierarchical groups
• Cyclic matrices of weighted digraphs

This page was built for publication: Which digraphs with ring structure are essentially cyclic?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q984026)