Cospectral digraphs from locally line digraphs

descriptionPublicationkeyboard_double_arrow_right Article , Preprint 01 Jul 2016Embargo end date: 01 Jan 2016 Spain English Publisher:Elsevier BVJournal:Linear Algebra and its Applications, volume 500, pages 52-62 (issn: 0024-3795,

Copyright policy )

Authors: Dalfó Simó, Cristina; Fiol Mora, Miquel Àngel;

doi: 10.1016/j.laa.2016.03.014 , 10.48550/arxiv.1604.04448

arXiv: 1604.04448

handle: 10459.1/72568 , 2117/89900

Cospectral digraphs from locally line digraphs

- Summary
- Subjects
- Related research
  (1)
- Metrics

Abstract

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

Country

Spain

Related Organizations

Universitat Polite`cnica de Catalunya
Spain
University of Lleida
Spain
Universitat Politècnica de Catalunya
Spain

Keywords

adjacency matrix, Graph operations (line graphs, products, etc.), 05C20, 05C50, Directed graphs (digraphs), tournaments, Classificació AMS::05 Combinatorics::05C Graph theory, cospectral digraph, digraph, spectrum, Grafs, Diameter, Spectrum, FOS: Mathematics, Kautz digraph, Mathematics - Combinatorics, diameter, de Bruijn digraph, Àrees temàtiques de la UPC::Matemàtiques i estadística, Teoria de, Graphs and linear algebra (matrices, eigenvalues, etc.), Grafs, Teoria de, Adjacency matrix, Digraph, :Matemàtiques i estadística [Àrees temàtiques de la UPC], Teoria espectral (Matemàtica), Cospectral digraph, De Bruijn digraph, Combinatorics (math.CO), Spectral theory (Mathematics), :05 Combinatorics::05C Graph theory [Classificació AMS], Directed graphs

1 Research products, page 1 of 1

Sequence mixed graphs
2017IsAmongTopNSimilarDocuments

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	4
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average