Which digraphs with ring structure are essentially cyclic?

DOI10.1016/J.AAM.2010.01.005zbMATH Open1213.05107arXiv0910.3113OpenAlexW1991753382MaRDI QIDQ984026FDOQ984026

Pavel Chebotarev, R. P. Agaev

Publication date: 13 July 2010

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

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.

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

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

zbMATH Keywords

Laplacian matrixChebyshev polynomialLaplacian spectrumspanning treeweighted digraphDirected graphessential cyclicity

Mathematics Subject Classification ID

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

Cites Work

• The matrix-forest theorem and measuring relations in small social groups
• Eigenvalues of the Laplacian of a graph^∗
• Title not available (Why is that?)
• 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.
• Title not available (Why is that?)
• Laplacians and the Cheeger inequality for directed graphs
• Forest matrices around the Laplacian matrix
• The matrix of maximum out forests of a digraph and its applications
• Spanning tree formulas and Chebyshev polynomials
• Parallel concepts in graph theory
• On $W$-bases of directed graphs
• On the spectra of nonsymmetric Laplacian matrices
• Chebyshev polynomials and spanning tree formulas for circulant and related graphs
• Algebraic connectivity of directed graphs
• On proximity measures for graph vertices
• Spanning forests of a digraph and their applications
• Kernels of directed graph Laplacians
• Title not available (Why is that?)
• Bounds for eigenvalues of doubly stochastic matrices
• Flocks and formations
• Title not available (Why is that?)

Cited In (6)

• Complex adjacency spectra of digraphs
• Realizable cycle structures in digraphs
• On singularity and properties of eigenvectors of complex Laplacian matrix of multidigraphs
• Tight bound on parameter of surplus-based averaging algorithm over balanced digraphs
• Further results on digraphs with completely real Laplacian spectra
• Scale fragilities in localized consensus dynamics

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)