An algebraic approach to lifts of digraphs

DOI10.1016/J.DAM.2018.10.040MaRDI QIDQ2328094zbMATH OpenOpenAlexWikidataFDO

Authors C. Dalfó, Mirka Miller, Miquel Angel Fiol, Joe Ryan, Jozef Širáň

Publication date 9 October 2019

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

abelian groupadjacency matrixdigraphgeneralized Petersen graphlifted digraphquotient digraphregular partitionspectrumvoltage digraphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: We study the relationship between two key concepts in the theory of (di)graphs: the quotient digraph, and the lift $Gamm{a}^{alpha}$ of a base (voltage) digraph. These techniques contract or expand a given digraph in order to study its characteristics, or obtain more involved structures. This study is carried out by introducing a quotient-like matrix, with complex polynomial entries, which fully represents $Gamm{a}^{alpha}$. In particular, such a matrix gives the quotient matrix of a regular partition of $Gamm{a}^{alpha}$, and when the involved group is Abelian, it completely determines the spectrum of $Gamm{a}^{alpha}$. As some examples of our techniques, we study some basic properties of the Alegre digraph. In addition we completely characterize the spectrum of a new family of digraphs, which contains the generalized Petersen graphs, and that of the Hoffman-Singleton graph.

Recommendations

• The spectra of lifted digraphs
• On quotient digraphs and voltage digraphs
• scientific article; zbMATH DE number 1334620
• scientific article; zbMATH DE number 2174606
• Distance and adjacency spectra and eigenspaces for three (di)graph lifts: a unified approach

Cites work

• A note on the McKay-Miller-Širáň graphs
• Digraphs
• Graph theory
• scientific article; zbMATH DE number 5944463 (Why is no real title available?)
• scientific article; zbMATH DE number 1055145 (Why is no real title available?)
• scientific article; zbMATH DE number 1052834 (Why is no real title available?)
• scientific article; zbMATH DE number 1391729 (Why is no real title available?)
• Line Digraph Iterations and the (d, k) Digraph Problem
• On Moore Graphs with Diameters 2 and 3
• On quotient digraphs and voltage digraphs
• Problems in algebraic combinatorics

Cited in

(14)

• A group representation approach to balance of gain graphs
• The zeta functions of dihypergraphs and dihypergraph coverings
• Spectra and eigenspaces from regular partitions of Cayley (di)graphs of permutation groups
• Spectra and eigenspaces of arbitrary lifts of graphs
• The spectra of lifted digraphs
• A new approach to gross error detection for GPS networks
• From expanded digraphs to lifts of voltage digraphs and line digraphs
• On quotient digraphs and voltage digraphs
• Regular coverings and parallel products of Farey maps
• On the spectra of token graphs of cycles and other graphs
• Token graphs of Cayley graphs as lifts
• A general method to find the spectrum and eigenspaces of the k-token graph of a cycle, and 2-token through continuous fractions
• An effective approach to enumerate universal cycles for k-permutations
• On bipartite (1,1,k)-mixed graphs

This page was built for publication: An algebraic approach to lifts of digraphs

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