# Nonderogatory Directed Webgraph

Authors: Ilhan Hacioglu; Selman Bayat; Ozkan Yilmaz; Oktay Cesur
Journal: International Journal of Mathematics and Mathematical Sciences
 (2013)

---

## Abstract

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.


---

## Body

## 1. Introduction

LetG be a digraph with vertices labelled {1,2,…,n} and its adjacency matrix A(G) the n×n matrix whose ijth entry is the number of arcs joining vertex i to vertex j. 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 Mh(r) where r≥2,h≥3, are nonderogatory if and only if r=2.All graphs considered in the paper are directed, finite, loopless, and without multiple arcs.AdipathPn is a digraph (directed graph) with vertex set {v1,…,vn} and arcs (vi,vi+1) for i=1,…,n-1.AdicycleCn is a digraph with vertex set {v1,…,vn} having arcs (vi,vi+1) for i=1,…,n-1 and (vn,v1).ACartesian productG1×G2 of graphs G1 and G2 with disjoint point sets V1 and V2 and edge sets X1 and X2 is the graph with point set V1×V2 and u=(u1,u2) adjacent with v=(v1,v2) whenever u1=v1 and u2 adjacent with v2 or u2=v2 and u1 adjacent with v1.We use the definition as in [6]; for any arbitrary n×n matrix A, form the characteristic matrix xIn-A and let dj(x) denote the greatest common divisor (gcd) of all minors of order j of  xIn-A, j=1,2,…,n. These polynomials are called the determinantal divisor of xIn-A, and it follows that the quotients ij(x)=dj(x)/dj-1(x) for j=1,2,…,n(d0≡1) are also polynomials, called the similarity invariants of A.We use the following theorem from [6] to prove our main result.Theorem 1.
A matrixA(G) is nonderogatory if and only if its first n-1 similarity invariants are unity.


## 2. Diwebgraph

Thediwebgraph(m,n) denoted shortly by W→(m,n) is the digraph obtained by taking the Cartesian product of Cm and Pn.Without loss of generality, we assume that the arcs ofCm have clockwise orientation and the arcs of Pn have inward orientation as in Figure 1. For the algorithms described below, we used the prescribed labelling in the figure.Figure 1
C
5
×
P
3
=
W
→
(
5,3
).The adjacency matrixAmn×mn of W→(m,n) can be put in a block matrix form with blocks:(1)
Aii=A(Cm)for i=1,2,…,n,(2)
Ai,i+1=Im for i=1,2,…,n-1, where Im is m×m identity matrix,(3)
all the remaining blocks are zero matrices and if we write them explicitly,Aij=0  for i=1,2,…,n-2, j=i+2,i+3,…,n and Aij=0 for i=2,3,…,n, j=1,2,…,i-1, where 0 is m×m zero matrix.For example, the adjacency matrix of the graph in Figure1 is shown below:
(1)[010001000000000001000100000000000100010000000000010001000000100000000100000000000100010000000000010001000000000001000100000000000100010000001000000001000000000001000000000000000100000000000000010000000000000001000000000010000].We compute the invariant factors of characteristic matrixM=xI-A by using the following algorithms. In all the algorithms ri and ci denote the ith row and column, respectively, and ri↔rj(ci↔cj) means interchange of row (column) i with j.After Algorithm1, we obtain a block matrix with n blocks on the diagonal of the form
(2)Dm×m=diag[(-1)m-1(xm-1)1],
and all the other nonzero entries are
(3)Mij=(-1)r+s(ms-r)xm-(s-r),
where i=rm,r=1,2,…,n and j=sm,s=r+1,r+2,…,n.Algorithm 1
Input:
m, n and M=xI-A(W→(m,n))
(1)for  k=0→mn-m  by  m  do
(2)for  i=m→2  by  (-1)  do
(3)ck+i-1←x×ck+i+ck+i-1
(4)end for
(5)for  i=1→m-1  do
(6)rk+m←Mk+m,k+i+1×rk+i+rk+m
(7)end for
(8)if  (k<mn-m)  then
(9)for  i=k+2→k+m  do
(10)ci+m-1←(-1)×ci+ci+m-1
(11)end for
(12)end if
(13)for  i=1→m-1  do
(14)ck+i↔ck+i+1
(15)end for
(16)end for
(17)for  k=mn-m→m  by  (-m)  do
(18)for  i=mn-1→m+1  by  (-1)  do
(19)if  (imodm≠0)  then
(20)rk←Mki×ri+rk
(21)end if
(22)end for
(23)end for
Output:
MFor example, applying Algorithm1 to M=xI-A(W→(5,3)), we get(4)M=[-1000000000000000-1000000000000000-1000000000000000-1000000000000000x5-10000-5x4000010x300000-1000000000000000-1000000000000000-1000000000000000-1000000000000000x5-10000-5x40000000000-1000000000000000-1000000000000000-1000000000000000-1000000000000000x5-1].Now, we apply the next algorithm to put the matrixM in a simpler form.By applying Algorithm2, the matrix M whose nonzero entries are the first mn-n diagonal entries that are all 1 and the remaining n×n block N on the diagonal has the following form.Algorithm 2
Input:
m, n and M (output of the Algorithm 1)
(1)s←0
(2)for  k=m→mn  by  m  do
(3)for  i=k-s→mn-1  do
(4)ri↔ri+1
(5)ci↔ci+1
(6)end for
(7)s←s+1
(8)end for
(9)for i=1→mn-n  do
(10)ri←(-1)×ri
(11)end for
Output:
MThe entryN11=xm-1 and the remaining entries on the first row are given by (-1)i(mi)xm-i, where i=1,2,…,n-1.  The next row of N is obtained by deleting the last entry of the previous row, then cyclic shifting of it, and so on.For example, applying Algorithm2 to M (output of the Algorithm 1 applied to M=xI-A(W→(5,3))), we get
(5)M=[100000000000000010000000000000001000000000000000100000000000000010000000000000001000000000000000100000000000000010000000000000001000000000000000100000000000000010000000000000001000000000000000x5-1-5x410x30000000000000x5-1-5x400000000000000x5-1],(6)N=[x5-1-5x410x30x5-1-5x400x5-1].Now, we have to get the relationship between the invariant factors ofN.Lemma 2.
We have the following relationship between the determinant of some of the minors of(N);
(7)gcd(det(minorN11),det(minorNn1))=1.Proof.
det
(
minor
N
11
)
=
(
x
m
-
1
)
n
-
1 and det(minorNn1) can be computed by Algorithm 3, which turns our matrix into a diagonal one. Since the entries on the diagonal are not a factor of xm-1 the result follows.Algorithm 3
Input:
m, n and N
(1)U←minorNn1
(2)for  i=1→n-2  do
(3)ri+1←-(xm-1)Uii×ri+ri+1
(4)end for
Output:
UFor example, applying Algorithm3 to the 3 by 3 matrix N in the example, we get
(8)U=[-5x410x30-3x5+2x].Theorem 3.
W
→
(
m
,
n
) is nonderogatory.Proof.
By applying Lemma2, we get that the
(9)gcd(det(minorN11),det(minorNn1))=1.
Now, by Theorem 1, the result follows.Remark 4.
By changing the orientation of the arcs ofCm to be counterclockwise and the arcs of Pn to be outward and applying similar algorithms shown above, we can show that the formed new diwebgraphs are still nonderogatory.Further topics for research: are there any other digraphs formed by a Cartesian product that are nonderogatory?



---

*Source: 237948-2013-06-10.xml*