ars mathematica contemporanea
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 12 (2017) 167-182
Non-negative spectrum of a digraph
Irena M. Jovanovic *
School of Computing, Union University, Knez Mihailova 6, 11000 Belgrade, Serbia
Received 8 June 2014, accepted 29 March 2016, published online 26 November 2016
Digraphs are considered by means of eigenvalues of the matrix AAT, and similarly ATA, where A is the adjacency matrix of a digraph. The common spectrum of these matrices is called non-negative spectrum or N-spectrum of a digraph. Several properties of the N-spectrum are proved. The notion of cospectrality is generalized, and some examples of cospectral (multi)(di)graphs are constructed.
Keywords: Digraph, non-negative spectrum, multigraph, cospectrality, isomorphism. Math. Subj. Class.: 05C20
1 Introduction
Spectral (di)graph theory means usage of linear algebra tools and techniques in the study of (di)graphs. It is a very well developed mathematical field (see [8] or [6]) with many applications (see, for example, [2] and [15]).
For any (di)graph matrix M, one can build a spectral (di)graph subtheory, and then be able to study (di)graphs by means of eigenvalues of the matrix M. We will denote these eigenvalues M-eigenvalues. In general case, in order to avoid confusion, to any notion in the corresponding subtheory a prefix 'M' should be added. Frequently used graph matrices are the adjacency matrix A, the Laplacian L = D - A and the signless Laplacian Q = D + A, where D is a diagonal matrix of vertex degrees. The spectral (di)graph theory then consolidates all these particular subtheories together with interaction tools.
In this paper, digraphs are considered by means of eigenvalues of the matrix AAT, and similarly ATA, where A is the adjacency matrix of a digraph. The common spectrum of these matrices is denoted N-spectrum and called non-negative spectrum of a digraph. According to [5], the N-spectrum of a digraph was not considered in the mathematical
*The work is supported by Serbian Ministry of Education, Science and Technological Development, Projects 174033 and 11145003.
E-mail address: irenaire@gmail.com (Irena M. Jovanovic)
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
168
Ars Math. Contemp. 12 (2017) 111-126
literature so far. Since the matrices AAT and ATA appear in applications (see, for example, [11] and [12]), we believe that introduced notion and presented results could be useful to mathematicians and informaticians. Namely, N-spectrum can facilitate the examination of digraphs since frequently used adjacency matrix of a digraph is not symmetric in general case, and therefore its spectrum consists of complex numbers. It is well known that digraphs serve as models for different processes and phenomena in computer sciences, where some spectrally based techniques are used in investigations. By this approach some new conclusions and comparisons of existing results could be made.
The paper is organized as follows:
In Section 2 basic digraph terminology is given and some elementary facts related to the matrices AAT and AT A and their spectrum are pointed out. Since this paper represents the first mathematical paper on the N-spectrum, elementary observations useful for further work are presented in Section 3. In Section 4 the effect of certain digraph operations and transformations on the N-spectrum is studied. One family of N-cospectral digraphs is determined in this section. Structural similarity (i.e. values and layout of entries in the matrix) of the matrix AAT of some digraph with the adjacency or the signless Laplacian matrix of some multigraph, has motivated us to generalize the notion of cospectrality in Section 5. The study of cospectrality with respect to different (multi)(di)graph matrices could be useful in finding connections between different spectral subtheories that are based on these matrices, and, what is more important, in finding new pairs of cospectral (multi)(di)graphs in particular spectral subtheory. That way, certain pairs of multigraps that are cospectral with respect to the adjacency matrix are found. The study of spectral subtheory based on the signless Laplacian matrix is currently used (see, for example, [7]), so the paper is concluded with some examples of digraphs and multigraphs whose N- and Q-spectrum, respectively, are the same.
2 Preliminaries
Let D = (V (D), E (D)) be a digraph of order n with the set of vertices V (D) = {v1, v2, ..., vn}. The set of edges E(D) consists of ordered pairs of vertices, and we suppose that the loops, i.e. the edges of the form (vj, vj) are permitted, but multiple edges are not. The adjacency matrix A = [ajj ] of D is the binary matrix of order n, such that ajj = 1, if there is an edge from vj to vj, and otherwise ajj = 0.
If e = (vj, vj) is the edge of D, we say that vj is the initial vertex of e, while vj is the terminal vertex. The vertex vj G V(D) is the out-neighbour of the vertex vj G V(D) if there is the edge (vj, vj) G E(D). The vertex vk G V(D) is the in-neighbour of the vertex vj G V(D) if there is the edge (vk, vj) G E(D). The out-degree of vertex vj, denoted by outdegD(vj) or dD(vj), is the number of edges of which it is the initial vertex, while the in-degree of vj, denoted by indegD (vj) or dD (vj), is the number of edges of which vj is the terminal vertex. A loop at some vertex contributes 1 to both the in-degree and the out-degree of that vertex.
Let us suppose that the edges of D are ordered as ei, e2,..., em. The in-incidence matrix of D is the n by m matrix Bjn = [bjj] such that bjj = 1 if ej = (vk, vj) for some vertex vk, and otherwise bjj = 0. The out-incidence matrix Bout = [gjj] of the digraph D is the n by m matrix such that gjj = 1 if ej = (vj, vi) for some vertex v;, and otherwise gjj = 0. It is a matter of routine to check that A = BoutBfn holds.
The characteristic polynomial det(XI - A) of A is the characteristic polynomial of the
I. M. Jovanovic: Non-negative spectrum of a digraph
169
digraph D, and the eigenvalues of A are the eigenvalues of D. For the remaining notation and terminology related to digraphs, and also graphs, we refer the reader to [5], [2], [3], [1], [8] and [6].
In this paper we are interested in the structural characteristics of a digraph D related to the spectrum of matrices AAT and AT A, where A is the adjacency matrix of D. The matrices AAT and ATA are non-negative, square and symmetric. One can easily check that these matrices are positive semi-definite (see, for example, [14]), which means that their eigenvalues are non-negative.
The entries of the matrices AAT and AT A are characterised by the following proposition (see [12]):
Proposition 2.1. The (i,j)-entry of the matrix AAT (AT A) of D is equal to the number of common out-neighbours (in-neighbours) of vi and Vj. Diagonal entries of the matrix AAT (AT A) represent out-degrees (in-degrees) of the vertices of D.
According to the previous observations, one can introduce the following notation: Nout = AAT and Nin = ATA. The characteristic polynomial det(AI — Nin) of Nin is the Nin-characteristic polynomial of D, while the characteristic polynomial det(AI - Nout) of Nout is the Nout-characteristic polynomial of D. Since the spectrum of Nout and Nin is the same (see [14]), it can be denoted by the single name - the N-spectrum. Therefore, the characteristic polynomials N(x) of these matrices can be named the N-polynomials. However, we underline that through the investigation we mainly considered Nout(D) matrix of D, whose spectrum is denoted by ni > V2 > ... > Vn. The N-spectral radius pN(D) of D is defined to be the spectral radius of Nout(D), and similarly Nin(D).
Remark 2.2. For the N-spectrum n1,V 2,... ,Vn of a digraph D with m edges the following holds:
•	The numbers n1, V 2,... ,Vn are real and non-negative,
•	Vi + V2 + ... + Vn = m,
•	D is consisted of only isolated vertices if and only if n1 = n2 = ... = Vn =0. 3 Some basic results
In this section we give some elementary results that we will use in the subsequent sections.
Let us remind you that a digraph D is r-regular if the in-degree and the out-degree of each its vertex are equal to r. By use of the basic combinatorial principles for counting one can easily check that the row sum for each row of the matrix Nout(D) is equal to r + r(r — 1) = r2. Now, we can prove the following lemma:
Lemma 3.1. N-spectral radius pN (D) of a r-regular digraph D of order n is r2.
Proof. Since Nout(D) is the square, non-negative matrix with equal row sums, according to Theorem of Frobenius (see [4]) the spectral radius of this matrix is r2.	□
Remark 3.2. The eigenvector that corresponds to the N-eigenvalue r2 of a r-regular digraph D is all-1 vector.
170
Ars Math. Contemp. 12 (2017) 111-126
o
Example 3.3. The complete digraph of order n is the digraph Kn in which for each pair of vertices there is an edge, including a loop at each vertex. The N-characteristic polynomial of this digraph is:
Ng (x) = (x - n2)xn-1, and thus its N-spectrum is: n2, [0]n-1.
Here, and in the further text, an eigenvalue n of the multiplicity k is denoted by [n]k.
Let us now consider connected digraphs whose vertices do not have the common out-neighbours. If D = (V(D), E(D)) is such a digraph, then indegD(vi) < 1 must hold for each vertex vi e V(D).
Let us remind you that a rooted oriented tree, briefly rooted tree, is an oriented tree with a specific vertex v1, called the root, such that for every other vertex vj the path connecting v1 to vj is a directed path from v1 to vj. This means that D is connected, indeg(v1) = 0 and indegD (vi) = 1 for every other vertex vi of D, and vice versa according to Theorem 15.2 from [1]. It is obvious that vertices of a rooted tree do not have the common out-neighbours.
If in a digraph D whose vertices do not have the common out-neighbours there are at least two vertices such that their in-degrees are equal to 0, D would not have been connected, i.e. D would consist of at least two connected components.
Since in a rooted tree there is unique vertex v1 such that indeg(v1) = 0, one can add one extra edge to obtain a digraph where there is no pair of vertices with common out-neighbours. We distinguish two possibilities: this extra edge is a loop at v1, i.e. (v-i^/u^ or it is an edge (vx, v1), for exactly one vertex vx of a rooted tree. Hence, we can say that a resulting digraph is a unicyclic digraph derived from a rooted tree (Figure 1).
Figure 1: Unicyclic digraphs whose vertices do not have the common out-neighbours
That way, the following proposition is proved:
Proposition 3.4. D is a connected digraph whose vertices do not have the common out-neighbours if and only if it is a rooted tree or a unicyclic digraph that can be derived from a rooted tree.
Remark 3.5. Since the matrix Nout(D) of a connected digraph D such that there is no pair of vertices with the common out-neighbours in D is the diagonal matrix of vertex degrees, the N-spectrum of D is: outdegD(vi), outdegD(v2),..., outdegD(vn).
I. M. Jovanovic: Non-negative spectrum of a digraph
171
Remark 3.6. The converse digraph Conv(D) of a digraph D is obtained by reversing the direction of each edge of D (see [2]). So, a digraph whose vertices do not have the common in-neighbours is the converse digraph of a rooted tree or of a unicyclic digraph that can be derived from a rooted tree.
Example 3.7. The N-characteristic polynomial of a rooted tree D is:
Nd(x) = xl J^J (x — outdeg(vi)),
ViEU (D)
where l is the number of vertices vx such that outdegD(vx) = 0, while U(D) c V(D) is the set of vertices whose out-degree is at least 1.
The digraph Pn is the special case of a rooted oriented tree. If V(Pn) = {vi, v2,..., vn } is the set of vertices of this digraph, then its set of edges consists of the pairs of vertices
(vi, vi+1), for i = 1, 2,...,n — 1. The N-characteristic polynomial of Pn is:
N^ (x) = x(x — 1)n-i.
1-regular digraph Cn is the special case of a unicyclic digraph derived from a rooted tree. Its N-characteristic polynomial is:
N^ (x) = (x — 1)n.	(3.1)
4 Some digraph operations and transformations
We open this section with the result related to the N-spectrum of the complement of a given regular digraph.
The complement DC = (V(DC),E(DC)) of a digraph D = (V(D),E(D)) has the vertex set V(DC) = V(D) and e e E(DC) if and only if e e E(D). Also, there is a loop at vertex vi in DC if and only if there is no loop at vi in D. Similarly to the proof of Theorem 2.1.2 from [6] for regular graphs we can prove the following:
Proposition 4.1. If the N-eigenvalues of a r-regular digraph D of order n are ni(D), i = 1,2,...,n, then the N-eigenvalues of DC are n1(DC) = (n — r)2 and ni(DC) = ni(D), i = 2, 3, ... ,n.
Proof. If Ad is the adjacency matrix of D and J is all-1 matrix, we find:
Nom(DC ) = J2 — Ad J — J AD + Ad AD = (n — 2r)J + Nout(D),
because the row sum for each row of AD is equal to r.	□
Let us denote by D the digraph obtained from a connected digraph D by deleting the edge (vi, vj). Then we have: Nout(D) = Nout(D ) + M. Here, M = [mpq] is the square matrix of order n such that mii = 1 and mii = mii = 1 for each pair of vertices vi, vi such that (vi ,vj), (vi ,vj) e E (D), where l e {1, 2,..., n} \ {i}.
Theorem 4.2. (Interlacing theorem - edge version) Let D be a connected digraph of order n whose N-spectrum is n1(D) > n2(D) > • • • > nn(D), and there is at least one
172
Ars Math. Contemp. 12 (2017) 111-126
vertex vj in D such that indeg D (vj) = 1. Let D be a digraph obtained from D by deleting an edge (viy vj). If the N-eigenvalues of D are ni(D ) > (D ) > • • • > nn(D ), then
m(D) >ni(D') > m(D) > m(iD) > ...Vn(D) > Vn(D') > 0.
Proof. Since the spectrum of the matrix M consists of [1] and [0]n-1, the proof follows from Courant-Weyl inequalities (see, for example [6]).	□
Remark 4.3. By considering Nin matrix of a digraph, one can prove that the previously given Interlacing theorem holds also for a connected digraph D in which there is at least one vertex vj such that outdegD (vj) = 1, and for its subdigraph D obtained from D by deleting an edge (vj,vi), for some vertex vi.
In general case, such the N-eigenvalue interlacing does not hold. Namely, we have the following example.
Example 4.4. For the digraph D that is depicted on Figure 2 and the digraph D that is obtained from D by deleting the edge (1,3), the N-interlacing property holds, i.e. for the N-spectra of these digraphs we have the following inequalities: 4.390 > 3.879 > 1.838 > 1.653 > 1 > 1 > 0.544 > 0.468 > 0.228 > 0.
On the other hand, the N-eigenvalues of the digraphs D1 (Figure 2) and D1, that is obtained from Di by deleting the edge (1, 3), are 5.303 > 1.697 > 1 > 1 > 0, and similarly 4.115 > 1.764 > 1 > 1 > 0.139, so the N-interlacing property does not hold in this case.
Figure 2: Digraphs D and D1 from Example 4.4
Now, we will consider a digraph D* obtained from a connected digraph D by adding a
pendant edge at the vertex vi of D (i.e. an edge of the form (vx, vi) such that indegD* (vx) = 0 and outdegD* (vx) = 1, or an edge of the form (vi, vx) such that indegD»(vx) = 1 and outdego* (vx) = 0).
The following statement obviously holds.
Proposition 4.5. Let D* denotes a digraph obtained from a connected digraph D of order n by adding a pendant edge (vn+1, vi) at the vertex vi such that indegD (vi) = 0. Then the N-characteristicpolynomial of D* is: ND* (x) = (x — 1)No(x).	□
Let us denote by Dvk a digraph obtained from a digraph D by deleting the vertex vk,
and let (vi,vj-) = 1, if (vi,vj-) G E(D), and otherwise (vi,vj) = 0, for i,j G {1, 2,..., n}.
I. M. Jovanovic: Non-negative spectrum of a digraph
173
Definition 4.6. The digraph D™^ v ) is the out-(vk, vj)-shrinking of D if for the edge
(vfc, vj) in E(D), V(D^vo) = T^'vDD^vfc) and
E^U)) = E(Dvfc) U {(vj,Vj)|MD(vj,vfc) = 1, for each j = k}.
It is obvious that D°Ut v.) is a multidigraph in general case, and that if indegD (vj) = 1 then the matrix No„i(D?Vfci v,)) equals the matrix obtained from Noui(D) by deleting the k-th row and the k-th column.
Theorem 4.7. Let D* denotes a digraph obtained from a connected digraph D of order n by adding the pendant edge (vj,vj) at the vertex vj such that (vk,vj) G E(D) and rndegD (vj) = 1. Then
Nd, (x) = (x - 1)Nd(x) - N^o-t (x),
where ND°«t (x) is the N-characteristic polynomial of the digraph D™^ v ) that is the out-(vk, vj)-shrinking of a digraph D. Proof. Since indegD* (vj) = 2, we have
NOMi(D) r
NOMi(D*)=
1 ' (n+1)x(n+1)
where r = (0,..., 0, 0,..., 0)T is the vector of order n. The only no null coordinate
k
of the vector r corresponds to the common out-neighbour of vk and vj. By expanding the determinant of the matrix x/ - Noui(D*) by the last row we get:
Nd (x) = det (x/ - Nout(D*)) = (x - 1)ND(x) + (_1)(n+1)+k • det (M|r),
where the matrix M is obtained from x/ - Noui(D) by deleting the k-th column. Now, by expanding the determinant of the matrix (M|r) by the last column, we have:
Nd* (x) =(x - 1)Nd(x) + (-1)(n+1)+k(-1)k+n det (x/ - M=
(x - 1)Nd(x) - det ^x/ - M,
where M is obtained from the matix Noui(D) by deleting the k-th row and k-th column.
□
The line digraph L(D) of a digraph D (see, for example [5]) is the digraph whose vertices are the edges e1, e2,..., em of D such that there is an edge from ej to ej in L(D) if and only if the terminal vertex of ej equals the initial vertex of ej in D. If an edge ep is a loop at some vertex of D, then it becomes a loop at ep in L(D).
Some results on adjacency spectra and energies of iterated line graphs are exposed in [13]. On the similar way, we can define iterated line digraphs. If D = L0(D) is a digraph and L(D) = L1 (D) is its line digraph, then Lk (D), k = 2, 3,... defined recursively by the formula Lk (D) = L (Lk-1(D)) are the iterated line digraphs of D. The line digraph of an r-regular digraph is also r-regular digraph. More precisely, the line digraph L1 (D) of an r-regular digraph D of order n is the r1 = r-regular digraph of order n1 = nr. Consequently, Lk (D), k = 2,3,... is the rk = r-regular digraph of order nk = rnk-1 = rkn, where nk-1 is the order of the digraph Lk-1 (D).
174
Ars Math. Contemp. 12 (2017) 111-126
Theorem 4.8. The N-eigenvalues of the line digraph L(D) of a r-regular digraph D are:
[r2]n, [0](r-1)n.
Proof. We will determine the N-characteristic polynomial NL(D) of L(D) related to the
Nout(L(D)) matrix.
As L = BfnBout is the adjacency matrix of the line digraph L(D) of D (see [5]), where Bin and Bout are the in-incidence matrix and the out-incidence matrix of D, respectively, we find: Nout(L(D)) = rBfnBin. Here, we have that the diagonal matrix whose entries are the out(in)-degrees of vertices in D is: A = rl = BinBT = BoutBTut. According to Lemma 8.2.3. from [10] we get:
det (I - BinBin) = det (I - BTinBin), det (In - x-1rIn) = det (im - x-11Nout(L(D)^ .
det (xI„ - rIn) = de^xIm - 1 Nout(L(D))^ ,
i.e.
1
Furthermore we have:
and also
det ((x - r + !)/„ - In) = xn-m — det (rx/m - Nout(L(D))).
According to (3.1) we find:
N- (x - r + 1) = xn-mrmNL{D)(rx),
i.e.
Nl(d)(x) = xm-n(x - r2)n, and the proof follows.	□
Therefore the N-spectrum of the line digraph Lk (D) of a r-regular digraph D of order
n consists of [r2]nfc = [r2]nr and [0](r-1)nk = [0](r-1)r n, and hence we have the following corollary:
Corollary 4.9. Let D1 and D2 be two r-regular digraphs of order n (not necessary N-cospectral). Then for all k > 1 digraphs Lk (D1) and Lk (D2) are N-cospectral.
This way, we found a family of N-cospectral mates (i.e. the digraphs whose N-spectra are the same). We will continue examination of cospectrality in the next section.
5 Cospectrality relation
Let DM be the set of (multi)(di)graphs D of order n with the associated spectrum aM (D) related to some (multi)(di)graph matrix M. Let us introduce the relation p C DM x DM2 between sets DM and DM2, for some (multi)(di)graph matrices M1 and M2 in the following way: we say that the (multi)(di)graph D1 is in the relation p with the (multi)(di)graph D2, i.e. D1pD2 if and only if aMl (D1) = aM2 (D2). So, the relation p is the cospectrality relation, while D1 and D2 form an (M1; M2) -cospectral mate. That way, we can generalize the notion of cospectrality:
I. M. Jovanovic: Non-negative spectrum of a digraph
175
Definition 5.1. Let M1 and M2 be some (multi)(di)graph matrices. If the (multi)(di)graph D1 G DM is in the cospectrality relation p with the (multi)(di)graph D2 G D^2, i.e. the M1-spectrum of a (multi)(di)graph D1 is equal to the M2-spectrum of a (multi)(di)graph D2, then D1 and D2 are called (M1, M2)-cospectral (multi)(di)graphs.
It is obvious that p is the equivalence relation on the set DM, in which case (multi)(di)-graphs D1 and D2 such that D1pD2 are M-cospectral. As a result of the composition of the cospectrality relations, one can get some new pairs of cospectral (multi)(di)graphs, as follows.
Let us consider the set D^ of digraphs D of order n with the associated N-spectrum <7n (D). Clearly, N is related to Nout or Nin matrix of a digraph. Let us denote by GA+ and GA- the sets of out-multigraphs and in-multigraphs, respectively with the corresponding adjacency spectra. The in-multigraph M- g GA- and the out-multigraph M+ G GA+ are associated to a digraph D g D^ in the following way:
Definition 5.2. The in-multigraph M- = (V (MD), E(M-)) of adigraph D is the multigraph such that V(M-) = V(D), {vi,vj} G E(M-) if and only if there is a vertex vk G V(D) such that (vk, vi), (vk, vj) G E(D), and for each edge (vk, vi) in D there is a loop at vi in MD- .
Definition 5.3. The out-multigraph M+ = (V (M+),E(M+)) of a digraph D is the multigraph such that V(M+) = V(D), {vi, vj} G E(M+) if and only if there is a vertex vk such that (vi, vk), (vj, vk) G E(D), and for each edge (vi, vk) in D there is a loop at vi in
M+ .
According to the previous definitions, one can notice the cospectrality relation, say p-, between sets GA- and DN, and similarly the cospectrality relation, say p+, between sets DrN and GA+. As the result of the composition of relations p+ and p- the pairs of A-cospectral multigraphs M- and M+ are getting. That way we have:
Theorem 5.4. Multigraphs M- and M+ are A-cospectral.
So, the exposed construction is a way for obtaining new pairs of cospectral and not necessarily isomorphic multigraphs.
Example 5.5. The adjacency matrix of the in-multigraph M-, and similarly the outmultigraph M+, that is associated to the digraph D (which is depicted on Figure 3) is:
A(Md) = Nin(D) :
/ 2	0 2 0 \
0	110
2	13 0
^ 0	0 0 1 )
, and A(M+) = Nout(D) =
/2101 \ 1202 0 0 1 0 1202
Remark 5.6. Multigraphs M- and M+ associated to a digraph D are simple graphs only in the case when digraph D is a set of isolated vertices. If we permit existence of single
loops (i.e. loops of multiplicity one) in a simple graph, the primary digraph D can be Cn
or Pn. In this case, multigraphs M- and M+ are the sets of isolated loops or the disjoint unions of isolated loops and a single isolated vertex, and therefore M- and M+ are not only A-cospectral but also isomorphic.
176
Ars Math. Contemp. 12 (2017) 111-126
There are many examples where the multigraphs M— and M+ associated to a given digraph D are isomorphic, so the investigation of such multigraphs can be the subject of future research. If a primary digraph D is such that if (vj, vj) G E(D) then also (vj, vj) G E(D), for all vj, vj G V(D), it is obvious that the associated multigraphs M— and M+ will be isomorphic. We also have:
Proposition 5.7. Multigraphs M— and M+ associated to a digraph D of prime order, n > 2, with circulant adjacency matrix are isomorphic.
Proof. Since Njn(D) and Nout(D) are circulant matrices with the same eigenvalues, according to Theorem 1 from [9] they are permutationally similar.	□
For an integer n > 2 and a set S C {1,2,..., n - 1} the circulant digraph Cn(S) is a digraph such that V(Cn(S)) = {1, 2,..., n} and E(C„(S)) = {(i, i + j (modn)) : 1 < i < n, j G S}. Circulant digraphs are of great interest in the graph and digraph theory and their applications (see [2]).
Proposition 5.8.
isomorphic.
Multigraphs MD and M+ associated to a circulant digraph Cn(S) are
Proof. Since the converse digraph Conv(Cn(S)) of Cn(S) is isomorphic to Cn(S) (according to Proposition 2.14.1 from [2]) and since Njn(Cn(S)) = Nout(Conv(Cn(S))),
and similarly Nout(Cn(S)) = Njn(Conv(Cn(S))), the proof follows.	□
Example 5.9. The matrix Nout (D) of the 2-regular digraph D that is depicted on Figure 4 structurally corresponds to the signless Laplacian matrix Q(M) of the 2-regular graph M, also depicted on Figure 4, i.e.
/2 110 \ / 0 1 1 0 \	/2000 \ 1201 _ 1001 + 0200 1021 _ 1001 + 0020
\ 0 1 1 ^ \011^	\0002y
Nout(D) _
_ Q(M).
I. M. Jovanovic: Non-negative spectrum of a digraph
177
That way, one can notice the cospectrality relation p C DN x GQ between set DN of digraphs D of order n with the associated N-spectrum on (D) and the set GQ of multigraphs M of order n with the associated Q-spectrum oq (M).
Figure 4: Triplet of (N, A, Q)-cospectral digraph D, multigraph MD = M+ and graph M, respectively
This one and similar examples have motivated us to examine some new (N, Q)-cospectral mates. Furthermore, the multigraph M that makes (Q, N)-cospectral mate with a given digraph D can be used in determining some isomorphic multigraphs M- and M+, as follows:
Proposition 5.10. Let D be a connected r-regular digraph of order n. If Nout(D) = Q(M ) holds for some multigraph M, then r = 0 or r = 2.
Proof. We have Nout(D) = ri + C, where row sum of C is r(r - 1) for each row.
If Nout(D) is the signless Laplacian matrix of some multigraph without loops, then r = r(r — 1) holds, which implies r = 0 or r = 2. On the other hand, if Nout(D) is the signless Laplacian matrix of a multigraph with loops, then the number of loops at some vertex is (r — (r — 1)r)/2, which means that r = 0 or r = 2.	□
Remark 5.11. The statement from the previous proposition also holds in the case of the matrix Nin(D). Beside that, the multigraph M is the connected r-regular multigraph without loops. Therefore, we conclude that multigraphs M- and M+ associated to some 2-regular digraph D are isomorphic.
In order to examine (N, Q)-cospectrality, we will introduce some binary digraph operations. Still, according to the nature and the mutual relationships between entries of matrices Nout(D) and Q(M) of some digraph D and some multigraph M, respectively, one can suspect poor variety in terms of the structure and the order (i.e. number of vertices) of the (N, Q)-cospectral mates (that could be obtained by direct comparing of these matrices).
Let Di = (V(Di), E(Di)) and D2 = (V(D2), E(D2)) be two disjoint digraphs (i.e. digraphs with no common vertices nor edges).
Definition 5.12. The out-join D1 VouiD2 of two disjoint digraphs D1 = (V (D1), E(D1 )) and D2 = (V(D2),E(D2)) is the digraph D = (V(D),E(D)) such that V(D) =
178
Ars Math. Contemp. 12 (2017) 111-126
V(Di) U V(D2) and E(D) = E(Di) U E(D2) U {(u,v)|u e V(Di),v e V(D2)}, for each u e V(D1) and v e V(D2).
It is obvious that this digraph operation is not commutative, i.e. D1 VoutD2 = D2 Vout D1. Nout(D) matrix of the digraph D which is obtained by out-joining is:
where A1 and A2 are the adjacency matrices of digraphs D1 and D2, respectively, while J is all-1 matrix. Each entry of the j-th row of the matrix A2 JT is equal to outdegD2 (uj), where uj e V(D2).
In the same way one can define:
Definition 5.13. The in-join D1VinD2 of two disjoint digraphs D1 = (V(D1), E(D1)) and D2 = (V(D2),E(D2)) is the digraph D = (V(D),E(D))such that V(D) = V(D1) U V(D2) and E(D) = E(D1) U E(D2) U {(v,u)|v e V(D2),u e V(D1)}, for each u e V(D1) and v e V(D2).
Definition 5.14. The join D1VD2 of two disjoint digraphs D1 = (V(D1),E(D1)) and D2 = (V(D2), E(D2)) is the digraph D with the vertex set V(D) = V(D1) U V(D2), whose set of edges is E (D) = (E^V^t D2) U E ^^¿^2)) \ (E (D1) U E(D2)).
Proposition 5.15. Lei D = D1 VoutD2 be the digraph obtained by out-joining two connected disjoint digraphs D1 and D2 of orders n1 and n2, respectively. If Nout(D) = Q(M) holds for some multigraph M, then:
1. D1 is an isolated vertex, while D2 is a unicyclic digraph derived from a rooted tree.
(a)	if «4 = 1, then D =K^
(b)	if n1 = 2, then D1 is any of digraphs depicted on Figure 5,
(c)	if n1 = 3, then D1 is 1-regular digraph,
(d)	if n1 > 4, then there is no digraph D1 such that the statement given by the proposition holds.
Proof. Let us denote by V(D1) = {u1, u2,..., uni} and V(D2) = {v1, v2,..., vn2} the sets of vertices of digraphs D1 and D2, respectively.
If Nout(D) = [njj] is the signless Laplacian matrix of some multigraph M, then by observing its rows n1 + 1, n1 + 2,..., n1 + n2, one can conclude that the number:
2.	D1 =K1, while D2 is a rooted tree;
3.	D2 is an isolated vertex, and:
(1 - «1) outdegD2 (vp) -	npq(NOMi(D2)),
q=1,q=p
I. M. Jovanovic: Non-negative spectrum of a digraph
179
Figure 5: Digraphs from Proposition 5.15
for each p = 1,2,..., n2, is zero or even positive integer. This means that n1 = 1 and D2 is a digraph such that there are no vertices with the common out-neighbours or D2 is an isolated vertex.
In the former case, by observing rows 1, 2,... ,n1 of Nout(D), one concludes that:
outdegDl (uk) + n2 - m2,
for each k = 1, 2,... ,n1, is zero or even positive integer. Here m2 is the number of edges of D2, and the proof for statements 1. and 2. follows.
If D2 is an isolated vertex, then by observing rows 1, 2,... ,n1 of Nout(D), we get that:
outdegDl (uk) - ^ nkt(Nout(Di)) - nx +2, l=l,l = k
(5.1)
for each k = 1,2,..., ni, is zero or even positive integer. Let us consider the structure of
Di.
If n1 = 1 or n1 = 2, statements (a) and (b) follows from (5.1) by direct computation.
If n1 = 3, then 3 > outdegDl (uk) > 1 must hold for each k = 1, 2,3. Let us suppose that outdegD1 (ui) = 3. This implies indegD1 (ui) = indegD1 (U2) = indegD1 (u^) = 1, and since the out-degree of u2 and u3 must be at least 1, (5.1) will be a negative number for at least one k. One can analyse the case when outdegDl (u1) = 2 the same way. And finally, if outdegDl (u1) = 1, (5.1) is a non-negative integer if and only if J23=2 n1i(Nout(D1)) = 0. Since the out-degree of each vertex in D1 must be at least 1, D1 is 1-regular digraph.
Now, we will prove that there is no digraph Dni of order n1 > 4 such that (5.1) is zero or even positive integer. The proof will be carried out by use of the mathematical induction on the number of vertices n1 of Dni.
If n1 = 4, analogously as in the case when n1 = 3, one can show that there is at least one vertex, for example uk ,in D4 such that outdegDi (uk) <J2t=1 i=k nkl(Nout(D4))+2, where k G {1, 2,3,4}. Let us suppose that in a digraph Ds of order s > 4 there is at least one vertex such that (5.1) is a negative number. Let us consider a digraph Ds+1 of order s +1. By deleting an arbitrary vertex of Ds+1 we get a digraph Ds of order s, where, according to the inductive hypothesis, we can find at least one vertex, say ux, such that
outdegDs (ux) < ^ nxq(Nout(Ds)) + s - 2.
q=l,q=p
180
Ars Math. Contemp. 12 (2017) 111-126
If we return the removed vertex and all edges that are incident to it, we get the following inequalities:
outdegDs+1 (ux) < outdegDs (ux) + 1 <
s	s+1
^ nxq(Nout(Ds)) + s - 2+1 < ^ nxq(Nout(Ds+i)) + s - 1.
q=1,q=i	q=1,q=p
Hence, according to the principle of the mathematical induction, when D2 is an isolated vertex, there is no digraph D1 of order n1 > 4 such that Nout(D) = Nout(D1VoutD2) = Q(M).	□
Proposition 5.16. Let D = D1VD2 be the digraph obtained by joining two connected disjoint digraphs D1 and D2 of orders n1 and n2, respectively. If Nout(D) is the signless Laplacian matrix of some multigraph, then:
1.	D1 is an isolated vertex, while D2 is any of digraphs depicted on Figure 6;
2.	D1 = D2 =Ku-
3.	there are no digraphs D1 and D2 of orders n1,n2 > 3 such that the statement given by the proposition holds.
Figure 6: Digraphs from Proposition 5.16
Proof. Let us denote by V (D1) = {v1,v2,... ,vni} and V (D2) = {u1,u2,..., un2} the sets of vertices of digraphs D1 and D2, respectively. We have:
Nout(D) = Nout(D1VD2) =
Â! JT \f AT JT J A2 ) V J AT
Nout(D1) + JT J A1JT + JT AT (AJJt + JT ATT )T Nout(D2) + JJT
where A1 and A2 are the adjacency matrices of digraphs D1 and D2, respectively. If Nout(D) = [nij] is the signless Laplacian matrix of some multigraph, we have:
n1
(1 - n2) outdegD1 (v{) + (2 - n1) n2 -	nij(Nout(D1)) - m2 = 2w1, (5.2)
j = 1,j=i
for some non-negative integer w1 and i = 1,2,... ,n1, and
n2
(1 - n1) outdegD2 (uk)+ n1 (2 - v^) - ^ nij(Nout(D2)) - ™1 = 2w2, (5.3)
i=1,i=k
I. M. Jovanovic: Non-negative spectrum of a digraph
181
for some non-negative integer w2 and k = 1, 2,..., n2, where m1 and m2 are the numbers
of edges of digraphs D1 and D2, respectively.
First, let us prove that n1 < 3. Since (5.2) means that:
ni
(1 - U2) outdegDl (v) > (ni - 2) n2 + ^ nj(NOMi(Di)) + m-2
j=1,j=i
holds for each i = 1,2,..., n1, if we suppose that n1 > 3, we get:
ni
0 > 1+ ^ nij(Nout(D1)) + m2,
j=1,j=i
that is a contradiction. In the same way, one can prove that n2 < 3.
Statements 1. and 2. from the proposition one can get by direct analysis of (5.2) and (5.3).	□
References
[1]	J. A. Anderson, Discrete mathematics with combinatorics, Prentice Hall, 2nd edition, 2004.
[2]	J. Bang-Jensen and G. Z. Gutin, Digraphs. Theory, algorithms and applications, London: Springer, 1st edition, 2000.
[3]	M. Behzad, G. Chartrand and L. Lesniak-Foster, Graphs and digraphs, Wadsworth International Group, 1st edition, 1981.
[4]	A. Berman and R. J. Plemmons, Nonnegative matrices in the mathematical sciences, Academic Press, 1979.
[5]	R. A. Brualdi, Spectra of digraphs, Linear Algebra Appl. 432 (2010), 2181-2213, doi:10.1016/ j.laa.2009.02.033, http://dx.doi.org/10.1016/j.laa.2009.02.033.
[6]	D. Cvetkovic, P. Rowlinson and S. Simic, An introduction to the theory of graph spectra, volume 75 of London Mathematical Society Student Texts, Cambridge University Press, Cambridge, 2010.
[7]	D. Cvetkovic and S. K. Simic, Towards a spectral theory of graphs based on the signless Laplacian. II, Linear Algebra Appl. 432 (2010), 2257-2272, doi:10.1016/j.laa.2009.05.020, http://dx.doi.org/10.1016/j.laa.20 0 9.05.020.
[8]	D. M. Cvetkovic, M. Doob and H. Sachs, Spectra of graphs - Theory and applications, Johann Ambrosius Barth, Heidelberg, 3rd edition, 1995.
[9]	B. Elspas and J. Turner, Graphs with circulant adjacency matrices, J. Combinatorial Theory 9 (1970), 297-307.
[10]	C. Godsil and G. Royle, Algebraic graph theory, volume 207 of Graduate Texts in Mathematics, Springer-Verlag, New York, 2001, doi:10.1007/978-1-4613-0163-9, http://dx.doi. org/10.1007/978-1-4613-0163-9.
[11]	J. M. Kleinberg, Authoritative sources in a hyperlinked environment, in: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 1998), ACM, New York, 1998 pp. 668-677.
[12]	A. N. Langville and C. D. Meyer, A survey of eigenvector methods for Web information retrieval, SIAM Rev. 47 (2005), 135-161, doi:10.1137/S0036144503424786, http://dx. doi.org/10.1137/S0036144503424786.
182
Ars Math. Contemp. 12 (2017) 111-126
[13]	H. S. Ramane, H. B. Walikar, S. B. Rao, B. D. Acharya, P. R. Hampiholi, S. R. Jog and I. Gutman, Spectra and energies of iterated line graphs of regular graphs, Appl. Math. Lett. 18 (2005), 679-682, doi:10.1016/j.aml.2004.04.012, http://dx.doi.org/10.1016/ j.aml.2004.04.012.
[14]	D. Randall, A. O'Neill and A. Irani, CS 6550 - Design and analysis of algorithms, Lecture and notes, 2005, http://people.math.gatech.edu/~randall/AlgsF05/ nov14.pdf.
[15]	D. A. Spielman, Spectral graph theory and its applications, in: FOCS '07 Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007 pp. 29-38.