Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 6 (2013) 279–288
Unordered multiplicity lists of wide double paths
Aleksandra Erić
Faculty of Civil Engineering, University of Belgrade, 11000 Belgrade, Serbia
C. M. da Fonseca ∗
Department of Mathematics, University of Coimbra, 3001-501 Coimbra, Portugal
Received 20 February 2012, accepted 18 September 2012, published online 19 November 2012
Abstract
Recently, Kim and Shader analyzed the multiplicities of the eigenvalues of a Φ-binary
tree. We carry this discussion forward extending their results to a larger family of trees,
namely, the wide double path, a tree consisting of two paths that are joined by another
path. Some introductory considerations for dumbbell graphs are mentioned regarding the
maximum multiplicity of the eigenvalues. Lastly, three research problems are formulated.
Keywords: Graph, tree, matrix, eigenvalues, multiplicities, inverse eigenvalue problem.
Math. Subj. Class.: 15A18, 05C50
1 Preliminaries
For a given n × n real symmetric matrix A = (aij), we define the graph of A, and write
G(A), as the undirected graph whose vertex set is {1, . . . , n} and edge set is {ij | i 6=
j and aij 6= 0}. On the other hand, for a given (weighted) graph G, we may define
A(G) = (aij) to be the (real) symmetric matrix whose graph G(A) is G. We focus our
attention to the set
S(G) = {A ∈ Rn×n |A = AT and G(A) = G} ,
i.e., the set of all symmetric matrices sharing a common graph G on n vertices. Neverthe-
less, all results can easily be extended to complex Hermitian matrices.
If G is a tree, then the matrix A(G) is called acyclic. In particular, if G is a path, we
order the vertices of G such that A(G) is a tridiagonal matrix.
We will often omit the mention of the graph of the matrix if it is clear from the context.
∗This research was supported by CMUC - Centro de Matemática da Universidade de Coimbra and FCT -
Fundação para a Ciência e a Tecnologia, through European program COMPETE/FEDER.
E-mail addresses: eric@grf.rs (Aleksandra Erić), cmf@mat.uc.pt (C. M. da Fonseca)
Copyright c© 2013 DMFA Slovenije
280 Ars Math. Contemp. 6 (2013) 279–288
Let us denote the (algebraic) multiplicity of the eigenvalue θ of a symmetric matrix
A = A(G) by mA(θ). The (n− 1)× (n− 1) principal submatrix, formed by the deletion
of row and column indexed by i, which is equivalent to removing the vertex i from G, is
designated by A(G\i).
Among the linear algebra community, most of the results on multiplicities of eigen-
values are mainly confined to trees motivated by the Parter-Wiener Theorem [16] and to
Cauchy’s Interlacing Theorem.
For a more detailed account on the subject the reader is referred to [16]. We remark
that the Parter-Wiener Theorem was reformulated in the survey work [7], by the second
author, motivated by the earlier seminal work of C. Godsil on matchings polynomials [9,
10, 11]. The same approach produced a result for the multiplicities of an eigenvalue of a
matrix involving certain paths of the underlying graph, with many interesting applications
to general graphs [4].
Theorem 1.1. [6, 8] Let P be a path that does not contain any edge of any cycle in G.
Then
mA(G\P )(θ) > mA(G)(θ)− 1 . (1.1)
Since a tree has no cycles, the inequality (1.1) is true for any path in a tree, which
generalizes a result for the standard adjacency acyclic matrices [9].
The inequality (1.1) can provide us an upper bound for the multiplicity of an eigenvalue
of a graph. The next result was established by R.A. Beezer in [3, Lemma 2.1] and it gives a
lower bound. It was originally stated for standard adjacency matrices, but it can be proved
for weighted adjacency matrices.
Lemma 1.2. Let us suppose that H1, . . . ,Hk be graphs, and let v1, . . . , vt be additional
vertices. Construct a graph H by adding new edges that have one endpoint in the set
{v1, . . . , vt} and the other endpoint in a vertex of some Hi. If
A =

A1 0
. . . CT
0 Ak
C D
 ∈ S(H) ,
where Ai ∈ S(Hi), for i = 1 . . . k, D is a real diagonal block, and C has t rows, then
mA(λ) >
k∑
i=1
mAi(λ)− t . (1.2)
We remark that (1.2) is a special case of Cauchy-type interlacing theorems for block
Hermitian matrices. In fact, if λ is an eigenvalue of the upper block decomposition A1 ⊕
· · · ⊕ Ak, a block vector calculation shows that the dimension the eigenspace of λ of A is
at least as great as the dimension of the intersection of the eigenspace of λ of B and the
null space of C (for more details the reader is referred to [15]).
Interestingly, Lemma 1.2 provides us an algorithm construct matrices of certain graphs
where the maximum multiplicity is attained. For example, let us consider the (4, 3)-tadpole
graph T
A. Erić and C. M. da Fonseca: Unordered multiplicity lists of wide double paths 281

1 
2 
3 
4

5

6

7
........................................... ........................................... ...........................................
....
....
....
....
....
....
....
....
....
...
....
....
....
....
....
....
....
....
....
....
........................................
....
....
....
....
....
....
....
....
....
...
Considering the path joining vertices 1 and 4 in (1.1) we see that, for any eigenvalue λ of
A ∈ S(T ), mA(λ) 6 2 (see also [2, 8]). On the other hand, from (1.2), setting A1 for
the Jacobi matrix whose graph is the path joining vertices 1 and 2 (an edge) and A2 for the
matrix whose graph is the cycle containing vertices 4, 5, 6, and 7, we have
mA(λ) > mA1(λ) +mA2(λ)− 1 > 1 + 2− 1 = 2 .
Therefore, if we want to construct a matrix in S(T ) with an eigenvalue, say
√
2 of maximal
multiplicity, we may set
A1 =
(
1 1
1 −1
)
and
A2 =

0 1 0 −1
1 0 1 0
0 1 0 1
−1 0 1 0
 ,
constructed as in [5]. Then any matrix of the form
A =

−1 1 0 0 0 0 0
1 1 ∗ 0 0 0 0
0 ∗ ∗ ∗ 0 0 0
0 0 ∗ 0 1 0 −1
0 0 0 1 0 1 0
0 0 0 0 1 0 1
0 0 0 −1 0 1 0

has
√
2 (and, in this case, −
√
2 too) as an eigenvalue of maximal multiplicity 2.
In general, for a given (m,n)-tadpole Gm,n, if λ is an eigenvalue of A ∈ S(Gm,n) but
not eigenvalue of A(Cm), then λ is simple, from (1.1).
In this note, we show how to use inequality (1.1) to generalize a result on the maximum
multiplicity of an eigenvalue of a Φ-binary tree due to Kim and Shader [18] to a more
general family of trees: a wide double path. A wide double path is consists of two paths
that are joined by another path. Unordered multiplicity lists for two classes of wide double
paths are established generalizing previous results. At the end three new research problems
are pointed out.
First, we show how combining both bounds (1.1) and (1.2) in order to give necessary
and sufficient conditions for an eigenvalue has maximal multiplicity in the case of a dumb-
bell graph.
282 Ars Math. Contemp. 6 (2013) 279–288
2 Dumbbell graphs
A dumbbell graph is obtained by joining two cycles by a path. We will assume that the
length of this path is greater than 2. Nevertheless, all results are true for lower lengths, with
slight modifications.
Dumbbells graphs are a special class of bicyclic graphs, i.e., connected graphs in which
the number of edges equals the number of vertices plus one. These graphs are well con-
sidered in graph theory, combinatorics, and optimization literature [12, 13, 14, 19, 20, 21].
Much attention has recently been paid to the spectral properties of these non-acyclic graphs
[22, 23].
We start this section establishing an upper bound for the multiplicity of an eigenvalue
of a dumbbell graph.
Proposition 2.1. The maximum multiplicity of an eigenvalue of a dumbbell graph is 3.
Proof. Let P be the path intersecting both pendant cycles of the dumbbell graph D. Ob-
serve that the (disconnect) subgraph D\P is the union of two paths. Then, from (1.1),
mA(D)(λ) 6 mA(D\P )(λ) + 1 6 2 + 1 = 3 ,
for any eigenvalue λ of D.
Next we characterize the matrices where an eigenvalue attains the maximum multiplic-
ity.
Proposition 2.2. Let D be a dumbbell graph and let P be the path intersecting both pen-
dant cycles C1 and C2 at the vertices v1 and v`, respectively. If λ is an eigenvalue of
A ∈ S(D) of multiplicity 3, then λ is an eigenvalue of A(C1 \ v1) and of A(C2 \ v`).
Proof. Again, by Theorem 1.1, if mA(D)(λ) = 3, then
mA(D\P )(λ) > 3− 1 = 2 .
Since D\P = (C1 \ v1) ∪ (C2 \ v`) and both C1 \ v1 and C2 \ v` are paths, λ must be an
eigenvalue of each A(C1 \ v1) and of A(C2 \ v`).
Corollary 2.3. LetD be a dumbbell graph and let P = v1v2 · · · v` be the path intersecting
both pendant cycles C1 and C2 at the vertices v1 and v`, respectively. If λ is an eigenvalue
of A ∈ S(D) of multiplicity 3, then λ is an eigenvalue of both A(C1) and A(C2).
Proof. Considering the path P ′ = v2 · · · v` and (1.1), we have
mA(D\P ′)(λ) > 2 .
Now we only have to observe that D \ P ′ = C1 ∪ (C2 \ v`) and mA(C2\v`)(λ) = 1.
Note that we can conclude a result more general than Corollary 2.3. In fact, λ should
be an eigenvalue of any tadpole graph obtaining by joining, for example, the path vi · · · v`,
for any i = 2, . . . , `− 1, to the cycle C2 at v`.
The next result is a straightforward consequence of (1.1).
A. Erić and C. M. da Fonseca: Unordered multiplicity lists of wide double paths 283
Proposition 2.4. Let D be a dumbbell graph and let P be the path intersecting both pen-
dant cycles C1 and C2 at the vertices v1 and v`, respectively. If λ is an eigenvalue of
A ∈ S(D) but neither an eigenvalue of A(C1 \ v1) nor of A(C2 \ v`) or neither an eigen-
value of A(C1) nor of A(C2), then mA(λ) = 1, i.e., λ is a simple eigenvalue of A.
As we mentioned before, Lemma 1.2 provides an interesting algorithm producing ma-
trices of certain graphs with eigenvalues of maximum multiplicity. For, let us consider the
real number λ. For a given path of order k1, let A1 be a tridiagonal matrix of order k1, with
eigenvalue λ, using (according Jean Favard) the simple et élégant Wendroff’s algorithm
[24], appeared a long time ago but somehow has not received so far the appropriate con-
sideration by the linear algebra community. Now, using the general algorithm established
in [5], it is possible to construct periodic Jacobi matrices, say A2 and A3, whose cycles are
of orders k2 and k3, respectively, with λ being an eigenvalue of both matrices. Let us set
A =

A1
A2 x
T yT
A3
x 0 0
y 0 0
 ∈ S(H) ,
where x is the 0, 1 vector with 1’s in the position 1 and k1 + 1 and 0 elsewhere, and,
analogously, y is the 0, 1 vector with 1’s in the position k1 and k1 +k2 +1 and 0 elsewhere.
Then λ is an eigenvalue of A of multiplicity 3. In fact, from (1.2),
mA(λ) > mA1(λ) +mA2(λ) +mA3(λ)− 2 = 1 + 2 + 2− 2 = 3 .
3 Maximum multiplicities
We now turn back our attention to a family of binary trees. Recall that a binary tree is a tree
such that the degree of each vertex is no more than three. In this section we will consider
the family constituted by the trees of the following form: take five paths P1, . . . , P5 and
two vertices u and v; join any terminal vertex of P1, P2, and P5 to u; the other terminal
vertex of P5 and any terminal vertex of P3 and of P4 are added to v. These trees can also
be seen as consisting of two paths that are joined by another path. Therefore, we will call
them wide double paths. The paths P1, . . . , P4 are the legs (or branches) of such tree.
In [18] Kim and Shader studied several spectral properties of the so-called Φ-binary
trees. It is a particular case of the trees under discussion now: P5 has size 1 (i.e., a single
vertex) and the longest legs among the four legs are connected to different terminal vertices.
Theorem 3.1. Let T be a wide double path andA ∈ S(T ). Then the maximum multiplicity
of an eigenvalue of A is 3.
Proof. We only have to apply (1.1), for example, to the path P1 − u− P5 − v − P3.
Theorem 3.2. For a given wide double path T , λ is an eigenvalue of A ∈ S(T ) of maxi-
mum multiplicity if and only if λ is an eigenvalue of each path P1, . . . , P5.
Proof. SetAi = A(Pi), for i = 1, . . . , 5. Let us assume first thatmA(λ) = 3. Considering
the path P1 − u− P5 − v − P3 in T , from (1.1), it follows
mA2(λ) +mA4(λ) > 3− 1 = 2 .
284 Ars Math. Contemp. 6 (2013) 279–288
Thus, mA2(λ) = mA4(λ) = 1. Analogously, we prove mA1(λ) = mA3(λ) = 1. It
remains to prove that mA5(λ) = 1. In fact, since P5 can be obtained from T deleting the
paths P1 − u− P2 and P3 − u− P4, we have again, from (1.1),
1 > mA5(λ) > mÃ(λ)− 1 > mA(λ)− 2 = 1 ,
where à = A(H), with H being the generalized star with center u and legs P1, P2, and
P5.
Conversely, if mAi(λ) = 1, for i = 1, . . . , 5, then
3 > mA(λ) >
5∑
i=1
mAi(λ)− 2 = 3 .
from Theorem 3.1 and (1.2).
Let us set `i for the order of the path Pi, with i = 1, . . . , 5, in a wide double path W .
Corollary 3.3. The number n3 of eigenvalues with multiplicity 3 of a wide double path is
at most min{`1, . . . , `5}.
Corollary 3.4. [18, Theorem 2(a)] Let T be a Φ-binary tree andA ∈ S(T ). Then there are
no eigenvalues of multiplicity 4 or more, and the number n3 of eigenvalues with multiplicity
3 is at most one. Furthermore, if λ ∈ σ(A) with mA(λ) = 3, then the diagonal entry of A
corresponding to the axis vertex of T is λ.
We now investigate the eigenvalues of multiplicity 2. The first result is a consequence
of Lemma 1.2 and Theorem 3.2.
Lemma 3.5. Let T be a wide double path and let A ∈ S(T ). If λ ∈ σ(A) is an eigenvalue
of exactly four of the paths P1, . . . , P5, then mA(λ) = 2.
As before, n2 denotes the number of eigenvalues of multiplicity 2 of a given matrix.
Theorem 3.6. Let W be a wide double path and r = min{`i + `j | i = 1, 2, j = 3, 4}.
Then
n2 6 r − 2n3 . (3.1)
Proof. By Theorem 3.2, if λ1, . . . , λn3 are the distinct eigenvalues of A of multiplicity 3,
then they must be (simple) eigenvalues of both A(P2) and A(P4). Taking into account
Lemma 3.5, the inequality (3.1) follows.
We remark that Theorem 3.2 is in fact much more general. An analogous result can be
proved for any generalized caterpillar, i.e., a tree for which removing the legs produces a
path, and the maximum multiplicity of any eigenvalue is equal to the number of legs minus
one. In particular we have the following result.
Lemma 3.7. Let S be a generalized star and A ∈ S(S). Then mA(λ) = 2 if and only if λ
is an eigenvalue of each leg.
Theorem 3.8. Let T be a wide double path and A ∈ S(T ). Then mA(λ) = 2 if and only if
λ is a simple eigenvalue of the paths P1, P2, and of the generalized star with center v and
legs P3, P4, P5, or is a simple eigenvalue of the paths P3, P4, and of the generalized star
with center u and legs P1, P2, P5.
A. Erić and C. M. da Fonseca: Unordered multiplicity lists of wide double paths 285
Proof. Let us assume that mA(λ) = 2. From (1.1), for any path P in T , mA(T\P )(λ) > 1.
Therefore, if λ is not an eigenvalue of P1 (P2), then it must be an eigenvalue of both P3
and P4. Moreover, if S denotes the generalized star with center u and legs P1, P2, P5, then
mA(S)(λ) > 1. The other assertion is set in a similar fashion.
The converse follows from (1.1) and (1.2).
We now address the question on the number n1 of simple eigenvalues of A ∈ S(W ).
Since
n = n1 + 2n2 + 3n3 = `1 + · · ·+ `5 + 2 ,
on the one hand, we have
n1 6 n . (3.2)
In fact, the equality is attained when we construct A(L1), . . . , A(L5), with distinct eigen-
values. On the other hand,
n1 = `1 + `2 + `3 + `4 + `5 + 2− 2n2 − 3n3
> `1 + `2 + `3 + `4 + `5 + 2− 2r + n3
> |`1 − `2|+ |`3 − `4|+ `5 + 2 . (3.3)
Interestingly, we observe that, from the lower bound (3.3), any matrix in S(W ) must have
at least `5 + 2 simple eigenvalues. This generalizes [18, Corollary 3].
4 Unordered multiplicity lists
Recall that if m1 > · · · > mk, with m1 + · · · + mk = n, are the multiplicities of the
distinct eigenvalues of an n-by-n symmetric matrixA, then (m1, . . . ,mk) is the unordered
multiplicity list (or list) of the eigenvalues of A. By unordered multiplicity list of a graph
G we mean the set of unordered multiplicity lists for all matrices in S(G).
Without loss of generality, we will assume that `1 > `2 and `3 > `4. Moreover, we
convention that for a finite sequence of real numbers a1, . . . , ai, with i 6 0, is empty.
We are able now to find the unordered multiplicity lists of the wide double path under
discussion.
Theorem 4.1. Let W be a wide double path of order n, with `1 > `2 and `3 > `4. Then
the set of unordered multiplicity lists of W consists of the positive integer lists of the form
(3, . . . , 3︸ ︷︷ ︸
n3
, 2, . . . , 2︸ ︷︷ ︸
n2
, 1, . . . , 1︸ ︷︷ ︸
n1
) , (4.1)
with 0 6 n3 6 min{`2, `4, `5}, 0 6 n2 6 `2 + `4 − 2n3, and n1 = n− 2n2 − 3n3.
Proof. From our discussion in the previous section, it is clear that any unordered multiplic-
ity list of W is of the form (4.1).
Conversely, let S1 (resp., S2) be the generalized star with center vertex u (resp., v) and
legsL1, L2, L5 (resp., L3, L4, L5). Now, for k = 0, . . . ,min{`2, `4, `5}, p = 0, . . . , `2−k,
and q = 0, . . . , `4 − k, let us consider the `1 + `5 − k + p+ 1 distinct real numbers
β1, . . . , β`4−k−q, θ1, . . . , θ`1−`4+`5+p+q+1
286 Ars Math. Contemp. 6 (2013) 279–288
strictly interlacing with the `1 + `5 − k + p (distinct) real numbers
λ1, . . . , λ`5 , α1, . . . , α`1−k, α̃`2−k−p+1, . . . , α̃`2−k ,
and the `3 + `5 − k + q + 1 distinct real numbers
α1, . . . , α`2−k−p, µ1, . . . , µ`3−`2+`5+q+p+1
strictly interlacing with the `3 + `5 − k + q (distinct) real numbers
λ1, . . . , λ`5 , β1, . . . , β`3−k, β̃`4−k−q+1, . . . , β̃`4−k .
Now we consider A ∈ S(W ) such that
σ(A(L5)) = {λ1, . . . , λk, λk+1, . . . , λ`5}
σ(A(L1)) = {λ1, . . . , λk, α1, . . . , α`2−k−p, α`2−k−p+1, . . . , α`1−k}
σ(A(L2)) = {λ1, . . . , λk, α1, . . . , α`2−k−p, α̃`2−k−p+1, . . . , α̃`2−k}
σ(A(S1)) = {λ1, λ1, . . . , λk, λk, α1, . . . , α`2−k−p, β1, . . . , β`4−k−q, θ1, . . . ,
θ`1−`4+`5+p+q+1}
σ(A(L3)) = {λ1, . . . , λk, β1, . . . , β`4−k−q, β`4−k−q+1, . . . , β`3−k}
σ(A(L4)) = {λ1, . . . , λk, β1, . . . , β`4−k−q, β̃`4−k−q+1, . . . , β̃`4−k}
σ(A(S2)) = {λ1, λ1, . . . , λk, λk, β1, . . . , β`4−k−q, α1, . . . , α`2−k−p, µ1, . . . ,
µ`3−`2+`5+q+p+1},
The existence of the Jacobi matrices is granted by [24] and the two generalized stars by
[17, Theorem 11].
It is clear that the unordered multiplicity list of A is
(3, . . . , 3︸ ︷︷ ︸
t3
, 2, . . . , 2︸ ︷︷ ︸
t2
, 1, . . . , 1︸ ︷︷ ︸
t1
) , (4.2)
with t3 = k, t2 = `2+`4−2k−p−q, and t1 = (`1−`2)+(`3−`4)+`5+2+k+2(p+q).
Note that 0 6 k + 2(p+ q) 6 2(`2 + `4).
Observe that with 1 = `5 6 `2, `4,6 `1, `3, we are able to recover the results in [18]
for Φ-binary trees. Moreover, Theorem 4.1 can also be applied for `5 = 0 [1, 17].
Finally, a tree is minimal provided there is a matrix such that number of distinct eigen-
values is equal to the diameter (counting edges) plus one. From Theorem 4.1, we conclude
that the wide double paths are minimal, for `2, `4 6 `1, `3 6 `5. In fact, with t3 = 0,
t2 = `2 + `4, and t1 = (`1 − `2) + (`3 − `4) + `5 + 2, since the number of distinct
eigenvalues is `1 + `3 + `5 + 2 and the diameter is `1 + `3 + `5 + 1.
5 Open problems
In this paper, we provided the solution for the inverse eigenvalue problem of a wide double
path, generalizing the results for the very particular case of the family of the so-called Φ-
binary trees, recently established. The approach adopted here is different, offering a general
result with a more concise proof.
A natural generalization a wide double path is when we have more than 2 legs adjacent
to the “central” vertices u and v. Let us suitably call such trees as wide double generalized
stars.
A. Erić and C. M. da Fonseca: Unordered multiplicity lists of wide double paths 287
Problem 1. Characterize the unordered multiplicity lists of a wide double generalized star.
It seems this is not a difficult problem to handle and an elegant characterization similar
to Theorem 4.1 may be achieved.
A more hard problem is related an analogous characterization for binary trees.
Problem 2. Characterize the unordered multiplicity lists of a binary tree.
Our results may also be seen as the starting point for a more meaningful study:
Problem 3. What are the unordered multiplicity lists of trees having maximum multiplicity
3?
Of course, from our approach, the previous question can be extended to general graphs.
Probably new techniques will need to be developed for this attractive and vast area of
research. Some computational experiments allow us to assert that there will be some sur-
prising multiplicity lists.
References
[1] F. Barioli and S.M. Fallat, On the eigenvalues of generalized and double generalized stars,
Linear Multilinear Algebra 53 (2005), 269–291.
[2] F. Barioli, S.M. Fallat and L. Hogben, Computation of minimal rank and path cover number
for certain graphs, Linear Algebra Appl. 392 (2004), 289–303.
[3] R.A. Beezer, Trees with very few eigenvalues, J. Graph Theory 14 (1990), 509–517.
[4] A. Erić and C.M. da Fonseca, Some consequences of an inequality on the spectral multiplicity
of graphs, submitted.
[5] R. Fernandes and C.M. da Fonseca, The inverse eigenvalue problem for Hermitian matrices
whose graphs are cycles, Linear Multilinear Algebra 57 (2009), 673–682.
[6] C.M. da Fonseca, A note on the multiplicities of the eigenvalues of a graph, Linear Multilinear
Algebra 53 (2005), 303–307.
[7] C.M. da Fonseca, On the multiplicities of eigenvalues of a Hermitian matrix whose graph is a
tree, Ann. Mat. Pura Appl. 187 (2008), 251–261.
[8] C.M. da Fonseca, A lower bound for the number of distinct eigenvalues of some symmetric
matrices, Electron. J. Linear Algebra 21 (2010), 3–11.
[9] C.D. Godsil, Spectra of trees, Ann. Discrete Math. 20 (1984), 151–159.
[10] C.D. Godsil, Algebraic Combinatorics, Chapman and Hall, New York and London, 1993.
[11] C.D. Godsil, Algebraic matching theory, Electron. J. Combin. 2 (1995), #R8.
[12] J.L. Gross and J. Chen, Algebraic specification of interconnection network relationships by
permutation voltage graph mappings, Math. Systems Theory 29 (1996), 451–470.
[13] P. Hansen, A. Hertz, R. Kilani, O. Marcotte and D. Schindl, Average distance and maximum
induced forest, J. Graph Theory 60 (2009), 31–54.
[14] P. Hell and X. Zhu, Adaptable chromatic number of graphs, European J. Combin. 29 (2008),
912–921.
[15] R.A. Horn, N.H. Rhee and W. So, Eigenvalue inequalities and equalities, Linear Algebra Appl.
270 (1998), 29–44.
288 Ars Math. Contemp. 6 (2013) 279–288
[16] C.R. Johnson, A. Leal Duarte and C.M. Saiago, The Parter-Wiener theorem: refinement and
generalization, SIAM J. Matrix Anal. Appl. 25 (2003), 352–361.
[17] C.R. Johnson, A. Leal Duarte and C.M. Saiago, Inverse eigenvalue problems and lists of mul-
tiplicities of eigenvalues for matrices whose graph is a tree: The case of generalized stars and
double generalized stars, Linear Algebra Appl. 373 (2003), 311–330.
[18] I.-J. Kim and B.L. Shader, Unordered multiplicity lists of a class of binary trees, Linear Algebra
Appl. (2011), doi:10.1016/j.laa.2011.07.006
[19] S. Kratsch and P. Schweitzer, Isomorphism for graphs of bounded feedback vertex set number,
in: H. Kaplan (ed.), Algorithm Theory - SWAT 2010, Lecture Notes in Computer Science 6139,
Springer, 2010, 81–92.
[20] J.H. Kwak and J. Lee, Isomorphism classes of cycle permutation graphs, Discrete Math. 105
(1992), 131–142.
[21] S.-M. Lee, K.-J. Chen and Y.-C. Wang, On the edge-graceful spectra of cycles with one chord
and dumbbell graphs, Congr. Numer. 170 (2004), 171–183.
[22] J. Wang, F. Belardo, Q. Huang and E.M. Li Marzi, Spectral characterizations of dumbbell
graphs, Electron. J. Combin. 17 (2010), #R42.
[23] J. Wang, Q. Huang, F. Belardo and E.M. Li Marzi, A note on the spectral characterization of
dumbbell graphs, Linear Algebra Appl. 431 (2009), 1707–1714.
[24] B. Wendroff, On orthogonal polynomials, Proc. Amer. Math. Soc. 12 (1961), 554–555.