- 52.52.1: Let G and H be the graphs in the following figure. G H Please find ...
- 52.52.2: Let n 3 be an integer. The Mobius ladder graph , denoted M2n, has 2...
- 52.52.3: Let G be a graph and let v be a vertex of G. Prove that .G v/ .G/ ....
- 52.52.4: . Let a; b be integers with a; b 3. The torus graph Ta;b has vertex...
- 52.52.5: Let G be a graph with just one vertex. It is correct to say that G ...
- 52.52.6: Let G be a properly colored graph and let us suppose that one of th...
- 52.52.7: Let G be a graph with n vertices that is not a complete graph. Prov...
- 52.52.8: Let G be a graph with n vertices. Prove that .G/ !.G/ and .G/ n=.G/
- 52.52.9: Let G D Kn;m. Determine jV .G/j and jE.G/j.
- 52.52.10: Let G be a graph with n vertices. Prove that .G/.G/ n
- 52.52.11: Let G be the seven-vertex graph in the figure. Prove that .G/ D 4
- 52.52.12: Let G be a graph with exactly one cycle. Prove that .G/ 3.
- 52.52.13: Let n be a positive integer. The n-cube is a graph, denoted Qn, who...
- 52.52.14: Suppose G has maximum degree > 1, but it has only one vertex of deg...
- 52.52.15: Let G be a graph with the property that .H / d for all induced subg...
- 52.52.16: Consider the graph in the figure. Notice that it does not contain K...
- 52.52.17: Suppose G is a graph with 100 vertices. One way to determine whethe...
- 52.52.18: In addition to coloring the vertices of a graph, mathematicians are...
Solutions for Chapter 52: Coloring
Full solutions for Mathematics: A Discrete Introduction | 3rd Edition
Characteristic equation det(A - AI) = O.
The n roots are the eigenvalues of A.
Circulant matrix C.
Constant diagonals wrap around as in cyclic shift S. Every circulant is Col + CIS + ... + Cn_lSn - l . Cx = convolution c * x. Eigenvectors in F.
Echelon matrix U.
The first nonzero entry (the pivot) in each row comes in a later column than the pivot in the previous row. All zero rows come last.
Ellipse (or ellipsoid) x T Ax = 1.
A must be positive definite; the axes of the ellipse are eigenvectors of A, with lengths 1/.JI. (For IIx II = 1 the vectors y = Ax lie on the ellipse IIA-1 yll2 = Y T(AAT)-1 Y = 1 displayed by eigshow; axis lengths ad
Current Law: net current (in minus out) is zero at each node. Voltage Law: Potential differences (voltage drops) add to zero around any closed loop.
Least squares solution X.
The vector x that minimizes the error lie 112 solves AT Ax = ATb. Then e = b - Ax is orthogonal to all columns of A.
Linear combination cv + d w or L C jV j.
Vector addition and scalar multiplication.
Markov matrix M.
All mij > 0 and each column sum is 1. Largest eigenvalue A = 1. If mij > 0, the columns of Mk approach the steady state eigenvector M s = s > O.
Multiplicities AM and G M.
The algebraic multiplicity A M of A is the number of times A appears as a root of det(A - AI) = O. The geometric multiplicity GM is the number of independent eigenvectors for A (= dimension of the eigenspace).
The pivot row j is multiplied by eij and subtracted from row i to eliminate the i, j entry: eij = (entry to eliminate) / (jth pivot).
Every v in V is orthogonal to every w in W.
Ps = pascal(n) = the symmetric matrix with binomial entries (i1~;2). Ps = PL Pu all contain Pascal's triangle with det = 1 (see Pascal in the index).
The diagonal entry (first nonzero) at the time when a row is used in elimination.
Projection p = a(aTblaTa) onto the line through a.
P = aaT laTa has rank l.
Rayleigh quotient q (x) = X T Ax I x T x for symmetric A: Amin < q (x) < Amax.
Those extremes are reached at the eigenvectors x for Amin(A) and Amax(A).
Right inverse A+.
If A has full row rank m, then A+ = AT(AAT)-l has AA+ = 1m.
R = [~ CS ] rotates the plane by () and R- 1 = RT rotates back by -(). Eigenvalues are eiO and e-iO , eigenvectors are (1, ±i). c, s = cos (), sin ().
Spectral Theorem A = QAQT.
Real symmetric A has real A'S and orthonormal q's.
Constant down each diagonal = time-invariant (shift-invariant) filter.
Vector v in Rn.
Sequence of n real numbers v = (VI, ... , Vn) = point in Rn.