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 .x1x2x3x4a1a2a3a4a5a6a7D:x1x2x3x4e1e2e3e 4e5e6e7G: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.

2 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. 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.

3 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. 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.

4 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. 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).

5 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 ).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.

6 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. 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.

7 ThenGis -regular. The adjacency matrixA=A(G) is a real symmetricn-square matrixwith all main diagonal entries 0. SinceGis -regular, is an eigenvalue ofA. LetIbe the identityn-square Matrix , andJbe ann-square Matrix all of whose entriesare 1. Thennis an eigenvalue ofJ, otherwise are 0. Noted(G) = 2. By , all main diagonal entries ofA2are , otherwise are 0 or 1, and the (i,j)-thentry ofA2is 0 if and only if the corresponding two vertices are adjacent inG, thatis the (i,j)-th entry ofAis 1. It follows thatA2+A ( 1)I=J.( )This implies thatJis a polynomial inA. SoAandJhave a common set ofeigenvectors. Suppose that one of these isXcorresponding to the eigenvalue .ThenAX= X, JX= this eigenvector, the expression ( ) supplies the relation 2+ 1 = any other eigenvector ofAcorresponding to an eigenvaluer.

8 ThenAY=rY, JY= ( ), we obtain the relationr2+r ( 1) = two other distinct eigenvalues:r1=12( 1 + 4 3 ), r2=12( 1 4 3 ).SinceAis a real symmetric Matrix , it has only real eigenvalues. Thus bothr1andr2are real Matrix Representation OF GRAPHS47If is such thatr1andr2are not rational, then each has multiplicity12(n 1)as an eigenvalue ofAsinceAis rational. Since all main diagonal entries ofAare 0,by a result on the trace of a Matrix , the sum of the eigenvaluesofAis 0. Namely +12(n 1)(r1+r2) = 12 2= 0.( )The value of satisfying ( ) is only = 2, for whichn= 5 and the correspondingundirected (2,2)-Moore graph is an undirected values of for whichr1andr2are rational are those for which there is anintegerssuch thats2= 4 3. Thusr1=12(s 1), r2= 12(s+ 1).Lettbe the multiplicity ofr1. Then the sum of the eigenvalues ofAis +ts 12+ (n 1 t) s 12= the relationsn= 1 + 2ands2= 4 3, we have thats5+s4+ 6s3 2s2+ (9 32t)s= 15.

9 ( )Since the equation ( ) requires solutions in integers, the only candidates forsarethe factors of 15. These possible solutions are:s= 1, t= 0, = 1, n= 2;s= 3, t= 5, = 3, n= 10;s= 5, t= 28, = 7, n= 50;s= 15, t= 1729, = 57, n= is no undirected graph of degree 1 and diameter 2. The theorem undirected (7,2)-Moore bound ism(7,2) = 50, the corresponding undi-rected (7,2)-Moore graph is determined by Hoffman-Singleton. The uniqueness ofthe undirected (3,2)- and (7,2)-Moore Graphs have been shown by Hoffman undirected (57,2)-Moore has order 3250, the corresponding undirected (57,2)-Moore graph might exist, but no one has been able to construct(or prove the nonex-istence of) such a graph so Let M be the incidence Matrix of a digraphGwithout loops, and let Mibe the Matrix obtained from Mby deleting theith row.

10 Then the algebraic cofactor of anyentry in MMTis equal to the determinant det (MiMTi), whereMTdenotes the transpose of Concepts of GraphsProof:Suppose that the vertex-set ofGis{x1,x2, ,xv}, and letN= that the entry in position (i,j) ofNisnij. ThenNis symmetric andnij= dG(xi) =d+G(xi) +d G(xi),forj=i; (xi,xj) (xj,xi),forj6= the sum of any row and the sum of any column ofNall are 0. It is a routinealgebraic exercise to show that the algebraic cofactors of all entries inMMThavethe same value (the exercise ). LetNijbe the algebraic cofactors ofnijinMMT, and, without loss of generality, supposeNij=N11, 1 i,j 1be the first row vector ofM. ThenN=MMT= 1M1 T1MT1 = 1 T1 1MT1M1 T1M1MT1!.Thus, we haveNij=N11= det (M1MT1), 1 i,j vas conclude this section with some remarks. LetAbe the adjacency Matrix ofan undirected graphGwith the vertex-set{x1,x2, ,xv},Mthe incidence matrixof any oriented graphDofG, and letBbe thev vdiagonal Matrix with themain diagonal entriesbii=dG(xi).