×

Graph eigenvalues under a graph transformation. (English) Zbl 1274.05223

Summary: For a graph \(X\) and a digraph \(D\), we define the \(\beta \) transformation of \(X\) and the \(\alpha \) transformation of \(D\) denoted by \(X^{\beta }\) and \(D^{\alpha }\), respectively. \(D^{\alpha }\) is defined as the bipartite graph with vertex set \(V(D)\times \{0,1\}\) and edge set \(\{\{(v_i,0),(v_j,1)\}\mid v_iv_j\in A(D)\}\). \(X^{\beta }\) is defined as the bipartite graph with vertex set \(V(X)\times \{0,1\}\) and edge set \(\{\{(v_i,0),(v_j,1)\}\mid v_iv_j\in A(\overrightarrow {X})\}\), where \(\overrightarrow {X}\) is the associated digraph of \(X\). In this paper we give the relation between the eigenvalues of the digraph \(D\) and the graph \(D^{\alpha }\) when the adjacency matrix of \(D\) is normal. Especially, we obtain the eigenvalues of \(D^{\alpha }\) when \(D\) is some special Cayley digraph.

MSC:

05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite