Spectra and elementary cycles of the digraphs with unique paths of fixed length

Authors
Citation
Yk. Wu et al., Spectra and elementary cycles of the digraphs with unique paths of fixed length, LIN ALG APP, 293(1-3), 1999, pp. 145-158
Citations number
11
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Mathematics
Journal title
LINEAR ALGEBRA AND ITS APPLICATIONS
ISSN journal
0024-3795 → ACNP
Volume
293
Issue
1-3
Year of publication
1999
Pages
145 - 158
Database
ISI
SICI code
0024-3795(19990515)293:1-3<145:SAECOT>2.0.ZU;2-B
Abstract
A digraph G, whose adjacency matrix A satisfies A(k) = J(n) - I-n, where J( n) is the n x n matrix of all ones, is called a digraph with unique paths o f fixed length Ii, or simply a UPFL-k digraph. We prove that all the UPFL-k digraphs of the same order are cospectral and have the same number of elem entary cycles of length l for each l less than or equal to k. We also provi de some techniques helpful for computing the spectrum and the numbers of sh ort elementary cycles of a UPFL digraph, including the determination of the numbers of reentrant paths of every fixed length in a UPFL digraph. At the end of the paper we point out an interesting relation between the number o f elementary cycles of the UPFL digraphs and the number of circular sequenc es with equal length and period. Our theorems generalize corresponding resu lts of Lam and Van Lint. (C) 1999 Elsevier Science Inc. All rights reserved .