| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 2079.1 | will these do? | CHEFS::STRANGEWAYS | Andy Strangeways@REO DTN 830-3216 | Fri Mar 14 1997 09:35 | 27 |
| Try:
o---o o
| | |
| | |
o---o and o---o---o
|
|
o o
If my calculations are correct, these share a characteristic
polynomial of x^5 - 4x^3.
I can't claim any great mathematical skill here, just luck. My
knowledge of multilinear algebra failed me dismally. However, I read once
that "almost all trees are cospectral", so I tried a selection of small
trees - with no result. I then started looking to see how the
characteristic polynomial might be changed by operations such as adding
or deleting a point, and stumbled on the "C4 + v" graph by serendipity.
Do you have any useful results in this area that you could share with
us?
Andy.
|
| 2079.2 | | SPECXN::DERAMO | Dan D'Eramo | Fri Mar 14 1997 19:28 | 5 |
| I verified the results of .-1 ... if A is the adjacency matrix
and I the identity matrix, then det(A - xI) is - (x^5 - 4x^3)
for both graphs in .-1.
Dan
|
| 2079.3 | random remarks | TPOVC::BUCHANAN | Choose a loop...then cut. | Mon Mar 17 1997 05:14 | 41 |
| Yes, I checked the eigenvectors, and it looks good.
Coo! What a surprise! The example that I was thinking of has 6 vertices
each, and each is connected. Can you find it? Are there any other
examples with a smaller number of vertices?
"Almost all trees are cospectral." is an interestingly terse claim.
Presumably, it means all trees with the same order. Or does
"cospectral" just refer to the eigenvalues, in which case two graphs of
different order could share the same eigenvalues, which differ in
multiplicity only.
Suppose that the coefficient of x^(n-i) in the c.e. is a_i, where n is
the order of the graph, G. Then if G is bipartite, and i is odd, then a_i
= 0. It follows that 0 is an eigenvalue of every bipartite graph of odd
order.
If G is a forest, then a_(2j) = the number of sets of j vertex-independent
edges in the graph. This comes from the fact that the graph has no
cycles.
Trees are forests. Forests are bipartite.
a_0 = 1
a_2 = m (number of edges) = n-1 for a graph.
a_4 = (m 2) - sum(vertices v)(d_v choose 2)
where (x y) is x-choose-y i.e. x!/y!(x-y)!, and d_v is the degree of
vertex v.
I would have thought that there is some intrinsic variability in a_4
over the set of all forests (or trees) of order n. It would surpise me
if "almost all" trees of order n share the same value of a_4. sum of
d_v over vertices = 2n-2. So the average value for a vertex is a little
less than 2. What is claimed is that sum(v)d_v^2 is constant over
almost all trees of order n.
I am not yet convinced.
Cheers,
Andrew.
|
| 2079.4 | terse => ambiguous | CHEFS::STRANGEWAYS | Andy Strangeways@REO DTN 830-3216 | Mon Mar 17 1997 06:25 | 14 |
| I found the reference:
New Directions in the Theory of Graphs, Academic Press, 1973.
A.J.Schwenk - Almost all trees are cospectral.
"For almost every tree there is another tree with the same
characteristic polynomial."
The claim might be better expressed as "Almost all trees belong to a
cospectral pair".
By exhaustive search, there is no pair of distinct, cospectral graphs
on fewer than 5 points.
Andy.
|
| 2079.5 | When is G IM to G'? | TPOVC::BUCHANAN | Choose a loop...then cut. | Tue Mar 18 1997 21:53 | 15 |
| Are there any other examples on 5 vertices?
Can you find my connected example on 6 vertices?
The best way to solve this would be to write a little program which
hunts through the possible graphs. The only real design issue is how to
efficiently tell whether two graphs are isomorphic.
I had a beautiful program in Prolog a while back which did this as
part of some wider functionality (I used it to explore Ramsey graphs),
but I think that work has vanished without trace. God, what happened to
Prolog: *there* was a decent programming language.
Let me abort this infinite descent into nostalgia...
Andrew.
|