Let L = D - A be the Laplacian matrix of a graph G of order n. Let
Λ(G,x) = Σk (-1)k ck xk = det(xI - L)
be the Laplacian characteristic polynomial of G and observe that its coefficients ck = ck(G) are nonnegative. It is known that if G is a tree, then its Laplacian coefficient ck 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 c0 = 1, c1 = 2(n-1), cn = 0. For trees, cn-1 = n, and cn-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 cl(T) is different from cl(T') (respectively, cr(T) is different from cr(T')). Clearly, l and r exist if and only if T and T' are not laplacian-cospectral. Let us write T <1 T' if cl(T) < cl(T') and T <2 T' if cr(T) < cr(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 ci(T) > ci(T')?
After these "warm-up" questions, a more complex problem comes to ones mind. We say that T majorizes T' if ci(T) ≥ ci(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