[PDF] References

1. The characteristic polynomial of either graph isl67

5.e(Kn) =2(n1);e(Kmn) =2pmn:

6. Use Lemma 3.25.

7. Use the previous exercise to find the eigenvalues of the two graphs.

160 Hints and Solutions to Selected Exercises

8. Note thatA(G1)=0 1

AandA(G2)=1 1

A;respectively. Use Lemma

9. Letnbe pendant and suppose it is adjacent ton1:Assume the result forTnfng

Chapter 4

1. A repeated application of Laplace expansion shows that det(L+J)is equal to

Theorem 4.8.

2. LetjV(G)j=nandjV(H)j=m:ThenL(GH) =L(G)

L(H):If

1;:::;lnandm1;:::;mmare the eigenvalues ofL(G)andL(H);respectively,

3. Use Theorem 4.11 and the arithmetic mean-geometric mean inequality.

4. Use Theorem 4.13.

5. Let(X;Y)be a bipartition ofT:Make all edges oriented fromXtoY:The result

6. For the first part, verify that(A+)0satisfies the definition of the Moore-Penrose

0(A0)+A+AA0=AA0(A+)0A+AA0:

0:Substituting in the previous equation and using the first part shows that

Chapter 5

1. Note that

2. LetBbethefundamentalcutmatrix.Thereexistsan(n1)(n1)nonsingular

3. The proof is similar to that of Theorem 5.13.

4. First show that detBB0[E(T1)jE(T1)]is the number of spanning trees ofGcon-

Chapter 6

1. LetAbe the adjacency matrix ofGand supposeu0 satisfiesAu=mu:There

Hints and Solutions to Selected Exercises 161

2. The Perron eigenvalue of a cycle and ofK1;4is 2:

3. Use Corollary 6.14.

4. IfGis strongly regular with parameters(n;k;a;c)thenGcis strongly regular

1=n2k+a:

5. For the first part use Theorem 6.25.

6. Letl1;:::;lnbe the eigenvalues ofA:SinceAis nonsingular, the eigenvalues

Chapter 7

1. The LaplacianLofK1;n1hasIn1as a principal submatrix. Therefore, the rank

4. Use a symmetry argument.

5. The first part is an easy consequence of Theorem 7.16. For the second part, using

6. Letf:V(G)! f0;1;1gbe defined by setting it equal to 0 onV1;1 onV2

7. This is an easy consequence of Theorem 7.20.

8. Use Exercise 7, above .

9. Letfi= (n+1)2i;i=1;:::;n:Note thatf01=0:Use (7.17).

Chapter 8

1 and 2. Follow an argument similar to that in the proof of Theorem 8.2.

3. Fora6=0 evaluateD1

5. Suppose(D1S)x=0 for some vectorx:Premultiply this equation by

0and use the formula forD1given in Theorem 8.9 to concludet0x=

0 and hence that(12

LS)x=0;whereLis the Laplacian ofT:Then

LS)x=0;and since12

L+Sis positive semidefinite, conclude that

7. For anyi;j;k2V(T);dij=dik+dkjmod 2:

8. Use (8.26) and thatL+;being positive semidefinite, is a Gram matrix, that

10. Observe thatIkis a principal submatrix of the Laplacian matrix ofT:Use

162 Hints and Solutions to Selected Exercises

Chapter 9

2. The resistance distance between any two vertices of the cycle is easily found

3. First prove the result when there is a cycle containingiandj:Then use the fact

4. By Theorem 9.12, ifxis ann1 vector orthogonal tot;thenx0Rx0:

6. Use (9.3) and Theorem 4.7.

7. There is a one-to-one correspondence between the spanning trees ofGnot con-

0(G)c(G)+c(G)c0(G)c(G)=1

9. Use Theorem 9.12, the multilinearity of the determinant and the fact that each

10. Assume thatnis a pendant vertex and that the formula holds forTnfng:Use

Chapter 10

1. Use the recursive definition of a threshold graph and induction.

2. We may encode a threshold graph by a binary sequenceb1;:::;bn;withb1=1:

3. Use the recursive definition of a threshold graph and induction.

4. Use the recursive definition of a cograph and the fact that the union of two Lapla-

5. Whether a graphGis a cograph or not can be checked recursively. Take the

6. Theeigenvalues ofL(G)are:nwith multiplicityjV1j;jV1jwithmultiplicityjV2j

1; and 0:The number of spanning trees inKmnGis

7. The eigenvalues ofL(G)are given by: 2r+2;2r+1;r+2 with multiplicityr;

Hints and Solutions to Selected Exercises 163

8. The eigenvalues ofL(KnK2)are:n+2 with multiplicityn1;nwith multi-

Chapter 11

1. Agraphisrankkcompletableifandonlyifitsbipartitecomplementhasamatch-

2. Use the definition of chordal graph. IfGis a split graph then so isGc:

5. LetGbe the graph withV(G) =f1;:::;7gand withijif and only if

6. Use the Jacobi identity.