The Math Forum

Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Math Forum » Discussions » Math Topics » discretemath

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Graph Theory characteristic polynomial problem
Replies: 0  

Advanced Search

Back to Topic List Back to Topic List  
Stephen Kauffman

Posts: 28
From: Baltimore
Registered: 7/7/05
Graph Theory characteristic polynomial problem
Posted: Oct 16, 2007 2:34 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

This is a problem I'm having difficulty solving completely. It concerns a
graph of m vertices with at least one vertex of degree m-1, which is
neccessarily connected so its incidence matrix has rank m-1.

(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^m-2)(x-m)

where a0 = number of spanning trees = the product of the roots of the middle

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

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 |T|x|T^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 m-2
where m is the number of vertices, then in regards to (i) above

p(x) = x h(1-x) (x-m)

But I can't prove this nor can I show that the roots of h(x) are also always
integers. Also we only have m-1 <= 2n+k <= m(m-1)/2, but this admits the
possibility that n > m-2 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, , 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

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.