Partitioned tensor products and their spectra (Q1361461)

The partitioned tensor product of graphs was introduced by \textit{C. Godsil} and \textit{B. McKay} in [Products of graphs and their spectra, Lect. Notes Math. 560, 61-72 (1975; Zbl 0402.05050)] as follows. Let \(G_0\) and \(G_1\) be directed graphs whose vertex sets have been partitioned into two disjoint subsets, \(V(G_i)= V_{i0}\cup V_{i1}\), \(i=0,1\pmod 2\). The partitioned tensor product \(G\underline{\times}H\) of \(G\) and \(H\) with respect to this partitioning is defined by replacing in \(G_0\) each vertex in \(V_{0i}\) with a copy of the induced subgraph \(G_1|V_{1i}\) and each arc that runs from \(V_{0i}\) to \(V_{0(i+1)}\) with a copy of the arcs of \(G_1\) that run from \(V_{1i}\) to \(V_{1(i+1)}\), where the indices are reduced mod 2. In op. cit. Godsil and McKay derived an identity involving the characteristic polynomials of \(G\underline{\times} H\). In the paper under review, this result is refined by showing how to calculate the characteristic polynomial of \(G\underline{\times}H\) explicitly in terms of \(G\) and \(H\).