In 'Spectral Conditions for the Reconstructibility of a Graph' Godsil and McKay give a short proof of an identity (Lemma 2.1) that relates the generating function for the number of closed walks starting at a vertex i to the characteristic polynomials of the graph G and the vertex-deleted subgraph G-i, but refer to a 'considerably longer proof'. Does anybody have any idea what that longer proof might be?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
In the paper it says that "the proof of Lemma 2.1 is due to the referee, and replaces our considerably longer proof". So there are only three people who could possibly remember what happened 37 years ago (the referee, Brendan and me), and I know I have forgotten, and the person whom I suspect was the referee has passed on.
But probably you did not want that information, and you're really asking for a alternative proof. What makes the proof in the paper short is the use of Cramer's rule, and I suspect the original argument simply did without this, at some cost.
-
$\begingroup$ Thanks, Chris. The reason I raised the question is that some identities for walk generating functions generalise trivially to identities for semi-edge walk generating functions, as in 'The Q-generating function for graphs with application' by Cui & Tian, but for closed semi-edge walks the use of Cramer's rule on the signless Laplacian doesn't give such a simple relation! Are there any analogous identities for semi-edge walks? $\endgroup$ Commented Jan 29, 2015 at 16:33
-
$\begingroup$ @James Tutte: I'd need to think about that, but semi-edge walks seem to be basically walks on the line graph, so something might be possible. $\endgroup$ Commented Jan 29, 2015 at 18:00
-
$\begingroup$ There is a fair chance that I have an old draft of this paper in my files, but it will be more than a week until I have a chance to look. Meanwhile, I don't remember either. $\endgroup$ Commented Jan 30, 2015 at 7:36