Characteristic Polynomial and Eigenvalues of the Anti-adjacency Matrix of Cyclic Directed Prism Graph

摘要

A prism graph is a graph which corresponds to the skeleton of an n-prism and therefore it is a cyclic simple graph. It is denoted Y_n (n > 3) where n is half the number of vertices. An n-prism graph has 2n vertices and 3n edges. In this paper, only regularly-directed cyclic prism graphs are investigated. The anti-adjacency matrix is applied as the graph representation. An anti-adjacency matrix of graph representation is a 0-1 matrix of size m × m where m is the number of vertices. The entry b_(ij) of an anti-adjacency matrix B(G) of directed graph G is 0 if there exists a directed edge from vertex V_i to vertex V_j and is 1 otherwise. The characteristic polynomial of the anti-adjacency matrix B(Y_n) of directed cyclic prism graph Y_n are obtained. The characteristic polynomial will be proved by observing the both cyclic and acyclic induced subgraphs of the directed cyclic prims graph. Furthermore, the anti-adjacency matrix of directed cyclic prism graph is found to have both real eigenvalues and complex eigenvalues which appear in conjugate pairs.