Line digraphs and coined quantum random walks
Simone Severini · 2002
Abstract. In this note, we give a characterization of the adjacency matrix of the line digraph of a regular digraph and we discuss a generalization.On the light of the characterization given, we remark that the underlying digraph of a coined quantum random walk is the line digraph of a regular digraph. 1. A characterization of the adjacency matrix of the line digraph of a regular digraph 1.1. Set-up. The notion of line digraph has been introduced by Harary and Norman [HN60] in 1960. A classic survey on line graphs and digraphs is [HB78]; a recent one is [P95]. Line digraphs are used in the design and analysis of interconnection networks (see e.g. [FYA84]). Line digraphs are also used in algorithms for DIRECTED MAX-CUT [CE90] and TRAVELLING SALESMAN [GKWS98]. Definition 1 (Line digraph). The line digraph − → LD of a digraph ( D = (V, A) is the