Let L = D - A be the Laplacian matrix of a graph G of order n. Let

Λ(G,x) = Σ_{k}
(-1)^{k} c_{k} x^{k} = det(xI - L)

be the Laplacian characteristic polynomial of G and observe that its
coefficients c_{k }= c_{k}(G) are nonnegative. It is known that if G is a tree,
then its Laplacian coefficient c_{k} counts the number of k-matchings in
the subdivision of G (where each edge of G is replaced by a path of length 2).
It is also known that c_{0} = 1, c_{1} = 2(n-1), c_{n} =
0. For trees, c_{n-1} = n, and c_{n-2} is equal to the Wiener
index (the sum of all distances between distinct vertices of G.

Given two trees T and T' of the same order, let l (resp. r) be the smallest (resp.
largest) integer such that c_{l}(T) is different from c_{l}(T')
(respectively, c_{r}(T) is different from c_{r}(T')). Clearly, l
and r exist if and only if T and T' are not laplacian-cospectral. Let us write T
<_{1} T' if c_{l}(T) < c_{l}(T') and T <_{2}
T' if c_{r}(T) < c_{r}(T').

**Problem 1:**
Could it happen that T <_{1} T' and that T' <_{2} T?

**Problem 2:**
Could it happen that T <_{1} T' and T <_{2} T', but there is
an index i such that c_{i}(T) >
c_{i}(T')?

After these "warm-up" questions, a more complex problem comes to ones mind.
We say that T *majorizes* T' if c_{i}(T)
≥ c_{i}(T') for every i = 0,...,n. It is known (see [1] and
references therein) that the path is the unique maximal and the star is the
unique minimal element among n-vertex trees with respect to this order.

**Problem 3 (Mohar [1]):**
What can be said about the majorizing ordering of all trees of order n. How
large chains and antichains of pairwise non-laplacian-cospectral trees are there?

A partial answer about the chains follows from the results in [1].

It would also be interesting to know how close to a lattice are we. To be more specific, let us define U(T,T') to be the set of all trees Z of order n = |T| = |T'| such that Z majorizes T and T' simultaneously.

**Problem 4:**
For which trees T and T' has U(T,T') only one minimal element up to
cospectrality, i.e., when are all minimal elements in U(T,T') cospectral?

Of course, the same question can be posed for the "meet" operation.

Bibliography:

[1] B. Mohar, On the Laplacian coefficients of acyclic graphs, submitted.

Send comments to Bojan.Mohar@uni-lj.si