Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Graph Theory characteristic polynomial problem
Posted:
Oct 16, 2007 2:34 AM


This is a problem I'm having difficulty solving completely. It concerns a graph of m vertices with at least one vertex of degree m1, which is neccessarily connected so its incidence matrix has rank m1.
(i) If one considers an incidence matrix, Phi, over a field of characteristic 0, ie the incidence matrix of a directed graph where the columns correspond to the edges and each column contains exactly one 1, one 1, and remaining entries 0, (all zeroes for a loop). Any assignment of edge orientations is acceptable here.
Now forming the Gram matrix, Phi Phi', for the type of graph above one obtains the characteristic polynomial,
p(x) = x(a0 + a1 x + a2 x^2 + ... + x^m2)(xm)
where a0 = number of spanning trees = the product of the roots of the middle factor.
The roots for this type graph seem always to be integers (for the few examples I've tried), but I haven't been able to prove this.
(ii) Second this polynomial seems to be related to another characteristic polynomial of a full rank ExE matrix that describes the system of fundamental cut sets and cycles of the graph relative to any given spanning tree.
The formation of this matrix is involved: 1. Let Phi(i) be obtained by deleting the ith row.
2. Let G = [(Phi(i)A' )^(1)] [Phi(i)B'] where A' selects the columns of Phi corresponding the branches of a given spanning tree, and B' selects the columns corresponding to the chords. G then is TxT^C and describes the system of fundamental cuts and cycles.
3. Form the full rank ExE matrix, Theta = I + (A'GB  B'G'A) = I + S, where the second terms on the right are skew symmetric. This is another way of describing the system of fundamental cuts and cycles of a given spanning tree. I was able to show that the determinant of Theta is the number of spanning trees by induction on the number of edges.
Now the characteristic polynomial of S has the form
f(y) = y^k(c0 + c2 y^2 + c4 y^4 + ... + y^2n)
where E = 2n + k and the the sum of the coefficients c0 + c1 + c4 + ... + 1 is the number of spanning trees.
If we rewrite the second factor as
h(x) = c0 + c1 x + c2 x^2 + ... + x^n
and pad h(x) with enough zero roots if neccessary so that its degree is m2 where m is the number of vertices, then in regards to (i) above
p(x) = x h(1x) (xm)
But I can't prove this nor can I show that the roots of h(x) are also always integers. Also we only have m1 <= 2n+k <= m(m1)/2, but this admits the possibility that n > m2 and in the few examples I've tried this never happens. I've haven't tried many examples though.
I've posted a paper I've written, http://www.bcpl.net/~smkauffm/gtlawatersigned.pdf , which discusses these two seemingly related polynomials in section 5.1 page 18, and section 7.1 page 37.
Any ideas, or where the problem has been treated before?  Stephen Kauffman strangerland@gmail.com



