Adjacency polynomials of digraph transformations

作者：Deng, Aiping^*; Feng, Mengyu; Kelmans, Alexander

来源：Discrete Applied Mathematics, 2016, 206: 15-38.

DOI：10.1016/j.dam.2016.01.032

• Adjacency polynomial
• Regular digraph
• (xyab)-transformation
• Cospectral digraphs

Let A(lambda, D) be the adjacency characteristic polynomial of a digraph D. In the paper Deng and Kelmans (2013) the so-called (xyz)-transformation D-xyz of a simple digraph D was considered, where x, y, z is an element of {0, 1, +, -}, and the formulas of A(lambda, D-xyz) were obtained for every r-regular digraph D in terms of r, the number of vertices of D, and A(lambda, D). In this paper we define the so-called (xyab)-transformation D-xyab of a simple. digraph D, where x, y, a, b is an element of {0, 1, +, -}. This notion generalizes the previous notion of the (xyz)-transformation D-xyz, namely, D-xyab = D-xyz if and only if a = b = z. We extend our previous results on A(lambda, D-xyz) to the (xyab)-transformation D-xyab by obtaining the formulas of A(lambda, D-xyab), where x, y, a, b is an element of {0, 1, +, -} and a not equal b, for every simple r-regular digraph D in terms of r, the number of vertices of D, and A(lambda, D). We also use (xyab)-transformations to describe various constructions providing infinitely many examples of adjacency cospectral non-isomorphic digraphs.

• 出版日期2016-6-19
• 单位东华大学; rutgers