Cospectral digraphs from locally line digraphs

Abstract

A digraph Γ =(V, E) is a line digraph when every pair of vertices u, v∈V 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 Γ is a locally line digraph. In this paper we give a new method to obtain a di-graph Γ′ cospectral with a given locally line digraph Γ with diameter D, where the diameter D′ of Γ′ 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.

This research is supported by the Ministerio de Ciencia e Innovación and the European Regional Development Fund under project MTM2014-60127-P, and the Catalan Research Council under project 2014SGR1147.