11
$\begingroup$

Is it known whether a (connected) graph is determined by its multiset of spanning trees? In other words, do any two non-isomorphic connected graphs have different multisets of spanning trees? By a multiset I mean the set of spanning trees (up to isomorphism) and the counts of how many times each occurs.

I cannot find counterexamples or positive results on this.

I see that a previous post has asked this question without considering the counts of each spanning tree.

$\endgroup$

2 Answers 2

13
$\begingroup$

I just found an example in the graph reconstruction literature (thanks Bob Krueger) of two non-isomorphic graphs that have the same multiset of spanning trees, in Sedlacek, J. (1974). The reconstruction of a connected graph from its spanning trees. Mat. Casopis’Sloven. Akad. Vied. 24, 307-314. They are depicted below.

Two non isomorphic graphs with different multisets of spanning trees

Also, they can be distinguished by their decks of node-deleted subgraphs, as the left graph has an 8-cycle as a node-deleted subgraph, while the right graph does not.

$\endgroup$
10
$\begingroup$

This area of graph theory is known as "graph reconstruction." The Reconstruction Conjecture (due to Kelly and Ulam) states that a graph (on at least 3 vertices) is determined by its multiset of subgraph obtained by deleting exactly one vertex. This multiset is called the deck of the graph. Kelly has a lemma that implies that you can compute the multiset of spanning trees from the deck of connected graphs. If a graph was determined by its multiset of spanning trees, then the reconstruction conjecture would be true for the graph.

It would be interesting to see if there are any graphs reconstructible from its deck but not its multiset of spanning trees.

$\endgroup$
3
  • $\begingroup$ Thanks for letting me know of this result by Kelly. So this problem of reconstruction from spanning trees seems rather hard, given how hard the classic node-deleted reconstruction conjecture is ... $\endgroup$
    – Cptq
    Commented Nov 16, 2021 at 21:46
  • $\begingroup$ Could you share the reference to the quoted Kelly's lemma, please? $\endgroup$ Commented Sep 23, 2022 at 0:48
  • $\begingroup$ @Bob Krueger I dont think your comment is correct. Kelly's lemma only works for subgraphs $H$ of $G$, such that $v(H)<v(G)$. $\endgroup$ Commented May 16, 2023 at 10:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .