1.10 Matrix Representation of Graphs

1 42 Basic Concepts of Matrix Representation of GraphsDefinitions:In this section, we introduce two kinds ofmatrix representationsof a graph ,that is, the adjacency Matrix and incidence Matrix of the graphGwith the vertex-setV(G) ={x1,x2, ,vv}can be described bymeans of matrices. Theadjacency matrixofGis av vmatrixA(G) = (aij),whereaij= (xi,xj) =|EG(xi,xj)|.For example, for the digraphDand the undirected graphGshown in Figure ,their adjacency matricesA(D) andA(G) are as (D) = 0 2 0 00 0 0 01 1 0 11 0 0 1 ,A(G) = 0 2 1 12 0 1 01 1 0 11 0 1 1.

2 X1x2x3x4a1a2a3a4a5a6a7D:x1x2x3x4e1e2e3e4 e5e6e7G:Figure :A digraphDand an undirected graphGTheincidence matrixof a loopless graphGis av matrixM(G) = (mx(e)), x V(G) ande E(G),where, ifGis directed, thenmx(e) = 1,ifxis the tail ofe; 1,ifxis the head ofe;0,otherwise,and ifGis undirected, thenmx(e) = 1,ifeis incident withx;0, example, for the digraphDand the undirected graphGshown in Figure ,the incidence matrixM(D a7) andM(G) are as (D a7) = 1 1 0 0 1 1 1 1 1 0 0 00 0 1 1 0 10 0 0 1 1 0 , Matrix Representation OF GRAPHS43M(G) = 1 1 0 0 1 1 01 1 1 0 0 0 00 0 1 1 0 1 00 0 0 1 1 0 2.

3 The adjacency Matrix or the incidence Matrix of a graph is another representationof the graph , and it is this form that a graph can be commonly stored in Matrix Representation of a graph is often convenient if one intends to use acomputer to obtain some information or solve a problem concerning the graph . Thiskind of Representation of a graph is conducive to study properties of the graph bymeans of algebraic = 1 2 ni1i2 in be a permutation of the set{1,2, ,n}. Then we obtain ann npermutationmatrixP= (pij) defined bypij= 1,ifj= (i);0, is not difficult to see that the adjacency matrices of two isomorphic graphsare permutedly similar.

4 In other words, assume thatAandBare the adjacencymatrices of two isomorphic graphsGandH, respectively, then there exists av vpermutation matrixPsuch thatA=P , the incidence matrices of two isomorphic graphsare permutedly equiv-alent. In other words, assume thatMandNare the incidence matrices of two iso-morphic graphsGandH, respectively, then there exist av vpermutation matrixPand an permutation matrixQsuch thatM= between Matrix and Graphical Representa-tions:It is these properties that makes us convenient to study structures of graphsby using their Matrix representations.

5 We now present a veryuseful result on theadjacency Matrix of a graph as Let A be the adjacency Matrix of a digraphGwith the vertex set{x1, x2, , xv}. Then the entry in position(i, j)of Akis the number of different(xi, xj)-walks of :The proof is by induction onk. The result is obvious fork= 1 sincethere existaij(xi,xj)-walks of length one if and only if there existaijedges from44 Basic Concepts of GraphsxitoxjinG. LetAk 1= a(k 1)ij and assume thata(k 1)ijis the number ofdifferent (xi,xj)-walks of lengthk 1 inG; furthermore, letAk= a(k)ij.

6 SinceAk=Ak 1 A, we havea(k)ij=vXl=1a(k 1)il alj.( )Every (xi,xj)-walk of lengthkinGconsists of an (xi,xl)-walk of lengthk 1, wherexl(1 l v) is adjacent toxj, followed by an edge fromxltoxj. Thus by theinduction hypothesis and the equation ( ), we have the desired should be noted that walks could not be replaced by paths inTheorem is easy to see that there is the unique (x,y)-walk of lengthnfor any pair(x,y) of vertices inB(d,n). We obtain from Theorem immediately that ifAis the adjacency Matrix ofB(d,n), thenAn=J, whereJis ann-square matrixall of whose entries are 1.

7 Similarly, ifAis the adjacency Matrix ofK(d,n), thenAn+An 1= Examples:We will, in Section this book, introduce an important application of theadjacency Matrix of a graph , specially Theorem , in Matrix theory. We heregive three examples, which are important results in graph theory, to show thatadjacency and incidence matrices are very useful for studying Example , we show that ifGis a strongly connected digraph of ordervand the maximum degree , thenv 1 + + 2+ + k 1+ k= k+ 1,for = 1; k+1 1 1,for > attaining this upper bound are called( ,k)-Moore following example is due to Plesnik and Znom (1974), and rediscovered byBridges and Toueg (1980).

8 Example There is no( , k)-Moore digraph for 2andk :Assume thatGis a ( ,k)-Moore digraph whose ordernreaches theMoore bound defined in ( ), and letAbe the adjacency Matrix ofG. By theexercise ,Gis a -regular and simple digraph. Furthermore, by Theorem , Matrix Representation OF GRAPHS45we haveI+A+A2+ +Ak=J,( )whereIis an identity square Matrix . The expression ( ) impliesthatJis apolynomial inA, and so the matricesAandJhave a common set of is not difficult to show that is an eigenvalue ofA(see the exercise ).

9 Letrbe any eigenvalue other than , and letXbe an eigenvector corresponding tor. Noting that the zero, as an eigenvalue ofJ, has the multiplicityn 1, we haveAX=rX,JX= ( ), we obtain the relation1 +r+r2+ +rk= 0.( )The expression ( ) shows thatrhas the multiplicity (k+1) as the unite root, ,rk+1= 1. Letr1,r2, ,rn 1ben 1 eigenvalues ofAother than . By , all the main diagonal entries ofAi(1 i k) are 0, that is,TrAi= 0, i= 1,2, , the sum of the eigenvalues ofAi i+n 1Xj=1rij= 0, i= 1,2 ,k.( )Sincerjrj=|rj|2= 1 =rk+1j, it follows thatr 1j=rj=rkj, whererjis theconjugate complex number ofrj.

10 Settingi= 1 andi=kin ( ), respectively, wehave =n 1Xj=1rj, k=n 1Xj= the conjugates of the above expressions and noting ( ), we have that =n 1Xj=1r 1j=n 1Xj=1rkj= k,which holds if and only if eitherk= 1 or = 1. This contradicts to our assumptionand, thus, the conclusion Example , a digraph with the maximum degree and diameter 2 hasorder at most 2+ . We have known that the Kautz digraphK( ,2) had order 2+ . Therefore,K( ,2) is a maximum ( ,2)-digraph, which is the unique knownmaximum ( ,2)-digraph up to Concepts of GraphsSimilarly, ifGis a connected graph of ordervand the maximum degree , thenv 1 + + ( 1) + + ( 1)2+ ( 1)k 1= 2k+ 1,for = 2; ( 1)k 2 2,for > attaining this upper bound are called( ,k)-Moore (Hoffman and Singleton, 1960) There is noundirected( ,2)-Moore graph for 6= 2,3,7, thatGis an undirected ( ,2)-Moore graph of ordern.