Nonderogatory Directed Webgraph

By assigning a certain direction to the webgraphs, which are defined as the Cartesian product of cycles and paths, we prove that they are nonderogatory. 1. Introduction Let be a digraph with vertices labelled and its adjacency matrix the matrix whose th entry is the number of arcs joining vertex to vertex . A digraph is nonderogatory if the characteristic polynomial and minimal polynomial of its adjacency matrix are equal. Computation of the minimal polynomial of a matrix is harder than the characteristic polynomial especially when the matrix is large. That is, why it is important to know when the matrix is nonderogatory. The ladder graphs are examples of nonderogatory graphs first studied by Lim and Lam [1]. Later, difans were added to this family by Deng and Gan [2]. After that, Gan [3], proved that the complete product of difans and diwheels is also nonderogatory [3]. Bravo and Rada [4], found a characterization of nonderogatory unicyclic digraphs in terms of Hamiltonicity conditions. In another article, Rada [5], showed that directed windmills where , are nonderogatory if and only if . All graphs considered in the paper are directed, finite, loopless, and without multiple arcs. A dipath is a digraph (directed graph) with vertex set and arcs for . A dicycle is a digraph with vertex set having arcs for and . A Cartesian product of graphs and with disjoint point sets and and edge sets and is the graph with point set and adjacent with whenever and adjacent with or and adjacent with . We use the definition as in [6]; for any arbitrary matrix , form the characteristic matrix and let denote the greatest common divisor (gcd) of all minors of order of , . These polynomials are called the determinantal divisor of , and it follows that the quotients for are also polynomials, called the similarity invariants of . We use the following theorem from [6] to prove our main result. Theorem 1. A matrix is nonderogatory if and only if its first similarity invariants are unity. 2. Diwebgraph The diwebgraph denoted shortly by is the digraph obtained by taking the Cartesian product of and . Without loss of generality, we assume that the arcs of have clockwise orientation and the arcs of have inward orientation as in Figure 1. For the algorithms described below, we used the prescribed labelling in the figure. Figure 1: . The adjacency matrix of can be put in a block matrix form with blocks:(1)？？ for ,(2)？？ for , where is identity matrix,(3)？？all the remaining blocks are zero matrices and if we write them explicitly,？？ ？？for , and for , , where is zero matrix. For example,