Factoring Distance Matrix Polynomials

Karen L. Collins Dept. of Mathematics Wesleyan University Middletown CT 06459-0128

Abstract

In this paper we prove that a vertex-centered automorphism of a tree gives a proper factor of the characteristic polynomial of its distance or adjacency matrix. We also show that the characteristic polynomial of the distance matrix of any graph always has a factor of degree equal to the number of vertex orbits of the graph. These results are applied to full k-ary trees and some other problems.

Adjacency matrices and their spectra have arisen naturally as a tool with which to study graphs. The idea of a distance matrix seems a natural generalization, with perhaps more specificity than that of an adjacency matrix. However, the spectra of neither adjacency matrices nor distance matrices characterizes even trees; see [12]. Distance matrices and their spectra have also arisen independently from a data communication problem studied by Graham and Pollack, [9], in 1971, in which their most important feature is their number of negative eigenvalues. See Graham and Lovász, [8], or [4] for a description of the problem.

Let G be a graph. Typically, the computation of the characteristic polynomial of the adjacency matrix of a graph G, CP A(G), has been related to finding certain kinds of subgraphs of the original graph. For instance, let T be a tree on n vertices. Then the each coefficient of CP A(T) can be computed knowing only the number of matchings in the tree with a fixed number of edges. Graham and Lovász have proven a similar theorem for distance matrices of trees, in which each coefficient of CP D(T) can be computed using linear combinations of the numbers of certain subforests with three different fixed numbers of edges, see [8]. The coefficients of the linear combinations are related to the degrees of vertices in the subforests. Thus it is much more difficult to compute these coefficients for distance matrices than for adjacency matrices.

In this paper we present a technique for finding proper factors of the characteristic polynomial of the distance (or adjacency) matrix of a tree. This can greatly simplify the process of finding the eigenvalues of the distance matrix. The method is to look for linearly independent vertex-centered automorphisms of the tree, and to include the information from the vertex orbits of the tree. Usually the obvious automorphisms and the vertex orbit component together are enough to multiply to the correct degree and we have the whole characteristic polynomial. We use this method to compute the characteristic polynomials of the distance matrices of some examples. We also provide a lower bound on the number of times that −2 is an eigenvalue of the characteristic polynomial of a tree, which is an improvement of [13]. Finally, we compute the characteristic polynomial of full k-ary trees as the product of a sequence of polynomials that we describe with linear recurrences. Basic definitions: Graphs are taken to be simple, with no multiple edges or loops, and connected. An automorphism of a graph G is a mapping from the vertex set of G to itself such that vertices u, v are adjacent if and only their images under the automorphism are adjacent. The automorphism group of G partitions the vertices into vertex orbits by two vertices are in the same vertex orbit if there exists an automorphism of G that takes one to the other. The adjacency matrix of a graph G with n vertices, A(G), is defined to be an n × n matrix with i, j entry 1 if vertex i and vertex j are adjacent and 0 otherwise. Its characteristic polynomial is CP A(G) = det(A(G) − λI). The distance matrix of a graph G with n vertices, D(G), is defined to be an n × n matrix with i, j entry the distance in the graph between vertex i and vertex j. Its characteristic polynomial is CP D(G) = det(D(G) − λI). Let T be a tree on n vertices, with distance matrix D(T). A leaf of a tree is a vertex with degree 1. An automorphism of a tree is said to be vertex-centered at v if the automorphism permutes some of the connected components of T − v and leaves the rest of T (including v) fixed. Let C be the complex numbers. Let e_{i} be the column vector with 1 in the i^{th} place and 0 otherwise. For any set S, let e_{S} = ∑_{s∈S} e_{s}. The full k-ary tree of length r, F_{r,k}, is defined inductively by F_{1,k} is the star with k edges, and F_{r,k} is F_{r−1,k} with k new edges added to each leaf. The root of F_{r,k} is the vertex of degree k in the original F_{1,k}. See [1, 11] for graph concepts; [4] for an introduction to adjacency matrices; [15] for linear algebra background.

We make use of the following linear algebra result.

Theorem 1 Let V be an n-dimensional vector space over C, A be an n × n matrix, and W be a t-dimensional subspace of V with basis w_{1}, w_{2}, …, w_{t}. Suppose that AW ⊆ W and let B be the t × t matrix whose i^{th} row is the coefficients from the expression of Aw_{i} as a linear combination of w_{1}, w_{2}, …, w_{t}. Then det(B − λI) divides det(A − λI).

Proof Let E be the change of basis matrix from the first t standard basis vectors to w_{1}, w_{2}, …, w_{t}. Then det(A − λI) = det(E^{−1}AE − λI). But the t × t upper left submatrix of E^{−1}AE is B and below B the matrix is zero, because AW ⊆ W. Thus det(E^{−1}AE−λI) equals det(B−λI) times another polynomial. □

The first part of our method involves using the vertex orbits of a graph.

Theorem 2 Let G be a graph with vertex orbits S_{1}, S_{2}, …, S_{r}. Let V =< e_{S_{i}} : 1 ≤ i ≤ r >. Let B_{G} be the r × r matrix whose i^{th} row is the coefficients from the expression of D(G)e_{S_{i}} as a linear combination of vectors in V. Then det(B_{G} − λI) divides CP D(G).

Proof We show that D(T)V ⊆ V. Let v be a vertex of T and row(v) be the row of D(T) corresponding to v. For vertices u, v, let d(u, v) be the distance from u to v in T. Then row(v)·e_{S_{i}} = ∑_{u∈S_{i}} d(u, v). Since every automorphism of G preserves distance, if v′ is in the same orbit as v, then ∑_{u∈S_{i}} d(u, v) = ∑_{u∈S_{i}} d(u, v′). We call this factor the orbit factor. □

For example, if G is vertex-transitive, then V has dimension 1, B_{G} is the 1 × 1 matrix whose single entry is the sum of any row of D(G), and this number is an eigenvalue of D(G). If G has no non-trivial automorphisms, then every vertex is in a different vertex orbit, and the orbit factor is the whole CP D(G).

The second part of our method for a tree T involves finding 2 or more copies of the same subtree in T.

Theorem 3 Suppose that tree T has a vertex-centered automorphism, π, with z as the center. Let U_{1} and U_{2} be connected components of T − z, such that π(U_{1}) = U_{2}. Let u_{1} be the vertex in U_{1} which is adjacent to z, and u_{2} = π(u_{1}). Then we can find a factor of CP D(T) of degree the number of orbits of U_{1}, considered as a rooted tree with root u_{1}.

Proof Let the vertex orbits of U_{1} with u_{1} as the root be S_{1}, S_{2}, …, S_{q}. Then the corresponding orbits of U_{2} are π(S_{1}), π(S_{2}), …, π(S_{q}). Let V_{z} =< e_{S_{j}} − e_{π(S_{j})} : 1 ≤ j ≤ q >. Clearly the vectors that generate V_{z} are independent, hence the dimension of V_{z} is q. We show that D(T)V_{z} ⊆ V_{z}. Let w be a vertex in T and row(w) be the row of D(T) that corresponds to vertex w. Let x(w) = row(w) · e_{S_{j}} − e_{π(S_{j})}. Any two vertices in S_{j} have the same distance to u_{1} and hence to z, and hence to any other vertex in T − U_{1}. Similar statements are true for π(S_{j}). Any two vertices in S_{j} ∪ π(S_{j}) have the same distance to z. Now if w is in T − {U_{1}, U_{2}}, then the distance from w to a vertex in S_{j} is equal to the distance from w to a vertex in π(S_{j}), hence we get x(w) = 0.

If w ∈ U_{1} then suppose w ∈ S_{l}. Let ŵ be another vertex in S_{l} and w̃ ∈ π(S_{l}). We show that x(w) = x(ŵ) = −x(w̃). For vertices v, v′ let d(v, v′) be the distance from v to v′. For any vertex w, let Y (w) = ∑_{v∈S_{j}} d(w, v) and πY (w) = ∑_{v∈π(S_{j})} d(w, v). Then x(w) = Y (w) − πY (w). Since w and ŵ are both in the same vertex orbit of U_{1}, Y (w) = Y (ŵ). On the other hand, πY (w) = πY (ŵ) as well, since w and ŵ have the same distance to z. Clearly Y (w) = πY (w̃), since U_{1} and U_{2} are isomorphic, and πY (w) = Y (w̃), since w and w̃ are the same distance from z. □

Corollary 4 Let T be a tree, and z a vertex with k ≥ 2 leaf neighbors. Then −2 is an eigenvalue of CP D(T) at least k − 1 times.

Proof In this case, U is the graph with one vertex. Let the leaves be l_{1}, l_{2}, …, l_{k}. Then the vectors e_{l_{1}} − e_{l_{2}}, e_{l_{2}} − e_{l_{3}}, …, e_{l_{k−1}} − e_{l_{k}} are independent, and each are eigenvectors of D(T), with eigenvalue −2. □

Corollary 5 Let S_{n} be the star with n+1 vertices. Then CP D(S_{n}) = (−1)^{n+1} (λ^{2} − 2(n − 1)λ − n)(λ + 2)^{n−1}.

Corollary 6 Let 2S_{n} be the tree with 2(n + 1) vertices in which there are two vertices of degree n + 1 and 2n vertices of degree 1. Then CP D(2S_{n}) = (−1)^{2(n+1)}(λ + 2)^{2(n−1)}(λ + n)(λ + 1)(λ^{2} − (5n − 1)λ − 9n).

Corollary 7 Let T be a tree, p be the number of leaves of T, and q be the number of vertices that are adjacent to a leaf. Then −2 occurs as an eigenvalue of D(T) at least p − q times.

Proof Every vertex that is adjacent to k leaves (for k ≥ 2) gives k−1 eigenvalues of −2. Thus there are at least p − q of them. □

This corollary is a minor improvement of a theorem of Merris, see [13]. The number of −2 eigenvalues of D(T) does not solely depend on the number of leaves, see Remark 11 below.

We now illustrate the utility of this method by computing CP D(F_{r,k}). To state our result, we need to introduce two sequences of polynomials which will appear as factors in CP D(F_{r,k}). A sequence of polynomials P_{n} can be equivalently described by a linear recurrence, a generating function or a linear combination of constants raised to the power n. These equivalences are discussed in general in [14]. It will be convenient to describe the first sequence of polynomials with a linear recurrence, and to describe the second by a generating function.

Let P_{i,k}(λ) be the polynomial of degree i, defined inductively by P_{0,k}(λ) = 1, P_{1,k}(λ) = −2 − λ, and P_{i+1,k}(λ) = −(2 + (k + 1)λ)P_{i,k}(λ) − kλ^{2}P_{i−1,k}(λ).

Let N(k, λ, x) = −k^{5}λ^{5}x^{5} + k^{3}λ^{3}x^{4}((3k + 1)λ + (2k + 2))
+k^{2}λx^{3}((3k + 3)λ^{2} + (2k + 6)λ + 3)
+kx^{2}((k + 3)λ^{2} + 4λ + 1) + λx
Let M(k, λ, x) = (kλx + 1)(kλ^{2}x^{2} + x(2 + (k + 1)λ) + 1)
·(k^{3}λ^{2}x^{2} + kx(2 + (k + 1)λ) + 1)

Let Q_{r+1,k}(λ) be the polynomial of degree r + 1, defined by Q_{1,k}(λ) = −λ and ∑_{n=1}^{∞} Q_{n,k}(λ)x^{n} = \frac{N(k,λ,x)}{M(k,λ,x)}.

Theorem 8 Let k ≥ 2, and let F_{r,k} be the full k-ary tree with maximum distance r from the root. Then

CP D(F_{r,k})(λ) = P_{1,k}^{(k−1)k^{r−1}}(λ) · P_{2,k}^{(k−1)k^{r−2}}(λ) ⋯ P_{r,k}^{k−1}(λ) · Q_{r+1,k}(λ)

Proof Notice that the degree of the right hand side above is the telescoping sum (k − 1)k^{r−1} + 2(k − 1)k^{r−2} + 3(k − 1)k^{r−3} + … + r(k − 1) + r + 1 = k^{r} + (−1 + 2)k^{r−1} + (−2 + 3)k^{r−2} + … + (−(r − 1) + r)k + (−r + (r + 1)) and this is indeed equal to ∑_{l=0}^{r} k^{l}, the number of vertices in a full k-ary tree. We use Theorem 3 to compute CP D(F_{r,k}), where F_{r,k} is the full k-ary tree with maximum distance r from the root, by finding independent vector spaces that are preserved under the action of D(T). For each vertex z in F_{r,k} not on the bottom level, z is joined to k isomorphic copies of the same rooted tree: let U_{j} be the rooted tree with its root the j^{th} from the left child of z. Let the top level of F_{r,k} be labelled 0 and the level at distance i from the top be labelled level i. If vertex z is on level i, then U_{1} = U_{2} = … = U_{k} = F_{r−i−1,k}. Therefore, using Theorem 3 exactly k−1 times on z by sending U_{1} to U_{2}, and U_{2} to U_{3}, …, U_{k−1} to U_{k}, we have D(F_{r,k})V_{z} ⊆ V_{z} for each of the k − 1 V′_{z}s. Therefore, we can find a factor of CP D(F_{r,k}), say P_{r−i,k}, of degree the number of orbits of F_{r−i−1,k}, which is r − i, that appears k − 1 times. Since there are k^{i} vertices on level i in the identical situation as z, this gives us (k − 1)k^{i} copies of P_{r−i,k} that divide CP D(F_{r,k}) (as long as all the vector spaces V_{z} for each z are independent). We also get a factor of degree r + 1 by taking the orbit factor V of the whole tree, F_{r,k}.

Fix r. Let C_{r} = ∑_{l=0}^{r} k^{l}. We first show that the k − 1 vector spaces V_{z} for each vertex z given by Theorem 3 are linearly independent. The vertex orbits of F_{r,k} are the levels of the tree. Let V_{j} =< each of the k − 1 V′_{z}s : z is on level j > for each level 0 ≤ j ≤ r. Let M be the C_{r} × t matrix with columns all the generating vectors of the V′_{z}s, and t = the number of all these vectors. All of the vector spaces given by Theorem 3 are generated by vectors with non-zero entries only in one orbit. Hence we need only consider a single vertex orbit of F_{r,k} at a time to determine if all the vector spaces are independent. Fix level i in F_{r,k}. Let M(i) be the k^{i} × t_{i} submatrix of M with columns the column vectors from each of V_{0}, V_{1}, V_{2}, …, V_{r} indexed by vertices on level i and t_{i} = the number of generating vectors in the V′_{j}s that have non-zero coordinates for vertices on level i.

Lemma 9 Let J be the k × 1 column vector of all 1′s. Then M(i) =

( \begin{matrix}J & 0 & … & 0 & M(i − 1) & 0 & 0 & … & 0 \\ −J & J & … & 0 & 0 & M(i − 1) & 0 & … & 0 \\ 0 & −J & & 0 & 0 & 0 & M(i − 1) & … & 0 \\ ⋮ & ⋮ & ... & ⋮ & ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & & −J & 0 & 0 & 0 & … & M(i − 1) \end{matrix} )

Proof (of lemma) Let 1 ≤ j ≤ r. Then

V_{0} =< e_{S_{j}^{1}} − e_{S_{j}^{2}} > + < e_{S_{j}^{2}} − e_{S_{j}^{3}} > + … + < e_{S_{j}^{k−1}} − e_{S_{j}^{k}} >

where S_{j}^{1} are the level j descendants of the leftmost child of the root of F_{r,k}, S_{j}^{2} are the level j descendants of the second from the left child of the root, etc. The only generating vectors from V_{0} with non-zero coordinates on level i are e_{S_{i}^{1}} − e_{S_{i}^{2}}, e_{S_{i}^{2}} − e_{S_{i}^{3}}, …, e_{S_{i}^{k−1}} − e_{S_{i}^{k}} and these appear above in M(i) as the first k − 1 columns. Once we have considered the contribution from the single vertex on level 0, what remains is k disjoint copies of F_{r−1,k}. By induction, this is k copies of M(i − 1). □

We also must include the vector of all 1′s from the orbit factor V, so let M′(i) = [J, M(i)] where J is the vector of all 1′s. Notice that M′(i) is a square k^{i} × k^{i} matrix by induction. We show that det(M′(i)) ≠ 0, and hence that all these vectors are linearly independent.

We can manipulate (without changing the determinant) the first k columns of M′(i) as if they were the k × k matrix M′(1). We multiply M′(1) on the right by the k × k matrix B = (b_{i,j}) where

b_{i,j} = \{ \begin{matrix}1 & if i = j \\ k + 1 − i & if j = 1 and 2 ≤ i ≤ k \\ 0 & otherwise \end{matrix}

Since B has determinant 1, det(M′(1)B) = det(M′(1)). It is easy to check that M′(1)B is a lower triangular matrix with determinant (−1)^{k−1}k. Therefore, | det(M′(i)) |= k(det(M′(i − 1)))^{k}. We have seen that det(M′(1)) = (−1)^{k−1}k and this is never zero, hence by induction, det(M′(i)) is never zero. Therefore the vectors are linearly independent. This gives us that

CP D(F_{r,k})(λ) = P_{1,k}^{(k−1)k^{r−1}}(λ) · P_{2,k}^{(k−1)k^{r−2}}(λ) ⋯ P_{r,k}^{k−1}(λ) · Q_{r+1,k}(λ)

where P_{i,k}(λ) = the factor of degree i that came from a vertex on level r − i. Clearly, P_{i,k}(λ) does not depend on the choice of r, as long as r ≥ i. We can compute P_{i,k}(λ) recursively by looking at F_{i,k}.

Fix r. In order to compute P_{r,k}(λ) recursively, we compute the matrix of the action of D(F_{r,k}) on V_{0} of F_{r,k}. Let N be the C_{r} × r matrix with columns {e_{S_{t}^{1}} − e_{S_{t}^{2}} : 1 ≤ t ≤ r} where S_{t}^{1} is the set of vertices in F_{r,k} at distance t from the top and descendants of the leftmost child of the top, and S_{t}^{2} are the descendants of the second from the left child of the root, on level i. (That is, N describes one of the k isomorphic spaces that comprise V_{0} of F_{r,k}.)

Now P_{r,k}(λ) is the characteristic polynomial of the r × r matrix P [k] that records the action of D(F_{r,k}) on N. That is, the i, j^{th} entry of matrix P [k] is the coefficient of e_{S_{j}^{1}} − e_{S_{j}^{2}} in the linear expansion of D(F_{r,k})(e_{S_{i}^{1}} − e_{S_{i}^{2}}). We need compute only row(j)·(e_{S_{i}^{1}} −e_{S_{i}^{2}}) for a single vertex j in orbit S_{j}^{1} to find the i, j^{th} entry of P [k] by symmetry. If i ≤ j, then vertex j has 1 vertex on level i at distance j − i; (k − 1) vertices on level i at distance (j − i + 2); (k^{2} − k) vertices on level i at distance (j − i + 4), etc. Hence row(j) in D(F_{r,k}) times e_{S_{i}^{1}} − e_{S_{i}^{2}} is (j−i)+(k−1)(j−i+2)+k(k−1)(j−i+4)+…+k^{i−2}(k−1)(j+i−2)−(j+i)k^{i−1} = −i+(2−i)(k−1)+(4−i)(k^{2}−k)+…+(i−2)(k^{i−1}−k^{i−2})−ik^{i−1} = −2(1+k+k^{2}+ …+k^{i−1}) = −2C_{i−1} If i > j, then vertex j has k^{i−j} vertices on level i at distance j −i; k^{i−j+1} −k^{i−j} vertices on level i at distance (j −i+2), etc. Hence row(j) in D(F_{r,k}) times e_{S_{t}^{1}} −e_{S_{t}^{2}} is k^{i−j}((i−j)+(i−j+2)(k−1)+(i−j+4)(k^{2}−k)+…+ (i+j−2)(k−1)k^{j−2}−(i+j)k^{j−1} = k^{i−j}(−j+(2−j)(k−1)+(4−j)(k^{2}−k)+…+ (j − 2)(k^{j−1} − k^{j−2}) − jk^{j−1}) = −2k^{i−j}(1 + k + k^{2} + … + k^{j−1}) = −2k^{i−j}C_{j−1}.

We perform some elementary row and column operations on det(P [k] − λI) to simplify taking its determinant. We subtract the l^{th} column from the (l+1)^{st} column, beginning with l = r − 1 (the first column remains the same). Finally we subtract k times new row l from new row l + 1 for l = 1 to r − 1. Our resulting matrix Z_{r} = (z_{i,j}) has

z_{i,j} = \{ \begin{matrix}0 & if | i − j |≥ 2 \\ −2 − λ & if i = j = 1 \\ −2 − (k + 1)λ & if i = j and i > 1 \\ λ & if i = j − 1 \\ kλ & if i = j + 1 \end{matrix}

By expanding out the last column, we get det(Z_{r}) = (−2−(k +1)λ)det(Z_{r−1})− kλ^{2}det(Z_{r−2}) Hence

P_{r,k}(λ) = −(2 + (k + 1)λ)P_{r−1,k}(λ) − kλ^{2}P_{r−2,k}(λ)

Now Q_{r+1,k}(λ) is the characteristic polynomial of the (r +1)×(r +1) matrix Q[k] of the action of D(F_{r,k}) on the orbit factor V =< e_{S_{i}} : 0 ≤ i ≤ r > where S_{i} is the set of level i vertices. To find the i, j^{th} entry of Q[k], we multiply row(j) of D(F_{r,k}) times e_{S_{i}}. This is the sum of all distances from a vertex on row j to each of the vertices on row i. Hence, if i < j, it is (j − i) + (k − 1)(j − i + 2) + k(k − 1)(j − i + 4) + … + k^{i−2}(k − 1)(j + i − 2) + k^{i−1}(k − 1)(j + i) = −2 − 2k − 2k^{2} − … − 2k^{i−1} + (j + i)k^{i} = −2C_{i−1} + (j + i)k^{i}. If i ≥ j, this is −2C_{j−1}k^{i−j} + (i + j)k^{i}. Hence Q_{r+1,k}(λ) is the determinant of the (r + 1) × (r + 1) matrix Z_{r+1} indexed by 0 ≤ i, j ≤ r with entries

z_{i,j} = \{ \begin{matrix}−λ & if i = j = 0 \\ j & if i = 0 and j > 0 \\ ik^{i} & if j = 0 and i > 0 \\ 2ik^{i} − 2C_{i−1} − λ & if i = j > 0 \\ (i + j)k^{i} − 2C_{i−1} & if j > i ≥ 1 \\ (i + j)k^{i} − 2k^{i−1}C_{j−1} & if i > j ≥ 1 \end{matrix}

Using matrix manipulations similar to those for the P′s, we get Z̃_{r+1} with entries

z̃_{i,j} = \{ \begin{matrix}−λ & if i = j = 0 \\ 1 + λ & if i = 0 and j = 1 \\ 1 & if i = 0 and j > 1 \\ k + kλ & if j = 0 and i = 1 \\ k^{i} & if j = 0 and i > 1 \\ λ & if j − i = 1 and i, j > 0 \\ kλ & if i − j = 1 and i, j > 0 \\ −2 − (k + 1)λ & if i = j > 0 \\ 0 & if | i − j |≥ 2 and i, j > 0 \end{matrix}

Let B_{r}(λ) be the determinant of Z̃_{r+1} with its first column and last row removed; and let D_{r} be the determinant of Z̃_{r+1} with its first column and first row removed. Then Q_{r+1,k}(λ) = −(2 + (k + 1)λ)Q_{r,k}(λ) − kλ^{2}Q_{r−1,k}(λ) + (−1)^{r}2k^{r}B_{r−1}(λ)−k^{r}D_{r−1}(λ). We also get B_{r}(λ) = λB_{r−1}(λ)+(−1)^{r−1}D_{r−1}(λ) and D_{r}(λ) = (−(k + 1)λ − 2)D_{r−1}(λ) − kλ^{2}D_{r−2}(λ). Doing the computations, we get

∑_{n=0}^{∞} D_{n}(λ)x^{n} = −\frac{kλ^{2}x^{2} + (2 + (k + 1)λ)x}{kλ^{2}x^{2} + (2 + (k + 1)λ)x + 1}

∑_{n=0}^{∞} B_{n}(λ)x^{n} = −\frac{kλ^{3}x^{3} − (2 + (k + 1)λ)λx^{2} + (1 + λ)x}{kλ^{3}x^{3} − (2 + (k + 1)λ)λx^{2} + (2 + (k + 2)λ)x − 1}

These two generating functions plus the recurrence give us the generating function for the Q_{r,k}(λ). □

Remark 10 Note that −2 is always a root of P_{4n+1,2}(λ), and hence that the given factorization for CP D(F_{r,k})(λ) is not complete over the integers.

Remark 11 Although Remark 10 shows that we may not have an exact count, at least we can bound the total number of distinct eigenvalues of CP D(F_{r,k}) from above by (_{2}^{r+2}).

Remark 12 Let F_{r,k} be the full k-ary tree with maximum distance r from the root. Then

CP A(F_{r,k})(λ) = R_{1,k}^{(k−1)k^{r−1}}(λ) · R_{2,k}^{(k−1)k^{r−2}}(λ) ⋯ R_{r,k}^{(k−1)}(λ) · R_{r+1,k}(λ)

where each R_{i,k}(λ) has degree i and ∑_{n=0}^{∞} R_{n,k}(λ)x^{n} = \frac{1}{1+λx+kx^{2}} .

Open Question: (L. Butler) Trees in general are not characterized by their characteristic polynomials of adjacency or distance matrices. Are k-ary trees special? In other words, are the full k-ary trees the only trees to have the distance matrix spectra described above?

References

[1] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, North-Holland, New York, 1976.

[2] K. L. Collins, Distance matrices of graphs, Ph.D. Thesis, MIT, Cambridge, MA (1986).

[3] K. L. Collins, On a conjecture of Graham and Lovász about distance matrices, Discrete Appl. Math. 25 (1989) 27-35.

[4] D. M. Cvetković, M. Doob, H. Sachs, Spectra of graphs, (Academic Press, New York, 1980).

[5] D. M. Cvetković, M. Doob, I. Gutman, and A. Torĝasev, Recent resultss in the theory of graph spectra, (North-Holland, Amsterdam, 1988).

[6] M. Edelberg, M. R. Garey, and R. L. Graham, On the distance matrix of a tree, Discrete Math. 14 (1976) 23-39.

[7] R. L. Graham, A. J. Hoffman and H. Hosoya, On the distance matrix of a directed graph, Journal of Graph Theory I (1977) 85-88.

[8] R. L. Graham and L. Lovász, Distance matrix polynomials of trees, Advances in Math. 29 (1978) 60-88.

[9] R. L. Graham and H. O. Pollack, Embedding graphs in squashed cubes, in: Springer Lecture Notes in Mathematics 303 (Springer-Verlag, Berlin/New York, 1973) 99-110.

[10] F. Harary, C. King, A. Mowshowitz, and R. C. Read, Cospectral graphs and digraphs, Bull. London Math. Soc. 3 (1971) 321-328.

[11] L. Lovász, Combinatorial problems and exercises, (North-Holland, New York, 1979).

[12] B. D. McKay, On the spectral characterization of trees, Ars Combinatoria III (1977) 219-232.

[13] R. Merris, The distance spectrum of a tree, preprint.

[14] R. Stanley, Enumerative Combinatorics: Volume I, (Wadsworth & Brooks/Cole Advance Books and Software, Monterey, California, 1986).

[15] G. Strang, Linear Algebra and its applications, (Harcourt Brace Jovanovich, San Diego, 1988).