×

Spectra of products of digraphs. (English) Zbl 1475.05107

A unified approach to the determination of eigenvalues and eigenvectors of specific matrices associated with directed graphs is presented. Matrices studied include the distance matrix, with natural extensions to the distance Laplacian and distance signless Laplacian, in addition to the adjacency matrix, with natural extensions to the Laplacian and signless Laplacian. Various sums of Kronecker products of nonnegative matrices are introduced to model the Cartesian and lexicographic products of digraphs. The Jordan canonical form is applied extensively to the analysis of spectra and eigenvectors. The analysis shows that Cartesian products provide a method for building infinite families of transmission regular digraphs with few distinct distance eigenvalues.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C20 Directed graphs (digraphs), tournaments
05C12 Distance in graphs
05C75 Structural characterization of families of graphs
05C76 Graph operations (line graphs, products, etc.)
15A18 Eigenvalues, singular values, and eigenvectors
15A21 Canonical forms, reductions, classification
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] M. Aouchiche and P. Hansen. Two Laplacians for the distance matrix of a graph.Linear Algebra Appl., 439:21-33, 2013. · Zbl 1282.05086
[2] M. Aouchiche and P. Hansen. Distance spectra of graphs: A survey.Linear Algebra Appl., 458:301-386, 2014. · Zbl 1295.05093
[3] F. Atik and P. Panigrahi. On the distance spectrum of distance regular graphs.Linear Algebra Appl., 478:256-273, 2015. · Zbl 1312.05077
[4] S. Barik, D. Kalita, S. Pati, and G. Sahoo. Spectra of graphs resulting from various graph operations and products: A survey.Special Matrices, 6(1):323-342, 2018. · Zbl 1423.05097
[5] A.E. Brouwer and W.H. Haemers.Spectra of Graphs. Springer, New York, 2011. · Zbl 1231.05001
[6] R.A. Brualdi. Spectra of digraphs.Linear Algebra Appl., 432:301-386, 2010.
[7] M. Catral, L. Ciardo, L. Hogben, and C. Reinhart. Spectral theory of products of digraphs. Preprint, available at https://arxiv.org/abs/2003.03412.
[8] D.M. Cvetkovi´c , M. Doob, and H. Sachs.Spectra of Graphs. Academic Press, New York, 1980.
[9] A.M. Duval. A directed graph version of strongly regular graphs.J. Combin. Theory, Ser. A, 47:1988. · Zbl 0642.05025
[10] F. Esser and F. Harary. Digraphs with real and Gaussian spectra.Disc. Appl. Math., 2:113-124, 1980. · Zbl 0435.05027
[11] R.L. Graham and H.O. Pollak. On the addressing problem for loop switching.Bell Syst. Tech. J., 50:2495-2519, 1971. · Zbl 0228.94020
[12] R. Hammack. Digraphs products. In: J. Bang-Jensen and G. Gutin (editors),Classes of Directed Graphs, Springer Nature, 2018. · Zbl 1407.05111
[13] R.A. Horn and C.R. Johnson.Matrix Analysis, second edition. Cambridge University Press, Cambridge, 2013. · Zbl 1267.15001
[14] R.A. Horn and C.R. Johnson.Topics in Matrix Analysis. Cambridge University Press, Cambridge, 1991. · Zbl 0729.15001
[15] G. Indulal. Distance spectrum of graphs compositions.Ars Math. Contemp., 2:93-110, 2009.
[16] L.K. Jørgensen. Non-existence of directed strongly regular graphs.Disc. Math., 264:111-126, 2003. · Zbl 1014.05074
[17] M. Klin, A. Munemasa, M. Muzychuk, and P.H. Zieschang. Directed strongly regular graphs obtained from coherent algebras.Linear Algebra Appl., 377:83-109, 2004. · Zbl 1030.05119
[18] P. Lancaster.Theory of Matrices. Academic Press, New York, 1969. · Zbl 0186.05301
[19] R. Reams. Partitioned matrices. In: L. Hogben (editor),Handbook of Linear Algebra, second edition, Chapman & Hall/CRC Press, Boca Raton, 2014
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.