Cospectral digraphs from locally line digraphs

DOI10.1016/J.LAA.2016.03.014MaRDI QIDQ272341zbMATH OpenOpenAlexFDO

Authors C. Dalfó, Miquel Angel Fiol

Publication date 20 April 2016

Published in Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

adjacency matrixdiameterspectrumdigraphcospectral digraphde Bruijn digraphKautz digraph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Directed graphs (digraphs), tournaments (05C20) Graph operations (line graphs, products, etc.) (05C76)

Abstract: A digraph $G=(V,E)$ is a line digraph when every pair of vertices $u,vinV$ have either equal or disjoint in-neighborhoods. When this condition only applies for vertices in a given subset (with at least two elements), we say that $G$ is a locally line digraph. In this paper we give a new method to obtain a digraph $G^{\prime }$ cospectral with a given locally line digraph $G$ with diameter $D$, where the diameter $D^{\prime }$ of $G^{\prime }$ is in the interval $[D-1,D+1]$. In particular, when the method is applied to De Bruijn or Kautz digraphs, we obtain cospectral digraphs with the same algebraic properties that characterize the formers.

Recommendations

• When a digraph and its line digraph are connected and cospectral
• On commutativity of two unary digraph operations: subdividing and line-digraphing
• On cospectral signed digraphs
• The spectra of subKautz and cyclic Kautz digraphs
• The spectra of some families of digraphs

Cites work

• scientific article; zbMATH DE number 3910417 (Why is no real title available?)
• scientific article; zbMATH DE number 1055145 (Why is no real title available?)
• scientific article; zbMATH DE number 3218572 (Why is no real title available?)
• An application of matrix theory to a problem in universal algebra
• Constructing cospectral graphs
• Graph theory
• Line Digraph Iterations and the (d, k) Digraph Problem
• Message Graphs
• The Polynomial of a Directed Graph
• The spectra of some families of digraphs

Cited in

(4)

• On commutativity of two unary digraph operations: subdividing and line-digraphing
• An improved upper bound for the order of mixed graphs
• When a digraph and its line digraph are connected and cospectral
• On mixed radial Moore graphs of diameter 3

This page was built for publication: Cospectral digraphs from locally line digraphs

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