1
$\begingroup$

What information does the automorphism group $\mathrm{Aut}(G)$ of a graph $G$ give us about the number of it's spanning trees?

If not in general, can anything be said about some special cases, for example, when $\mathrm{Aut}(G)$ is the symmetric group $S_r$ for some $r\leq |V(G)|$? What if $G$ is regular/strongly regular?

Improve this question
$\endgroup$
3
  • 6
    $\begingroup$ Consider a tree consisting of a long path except that at one end there are $r$ leaves with the same neighbour. Then the automorphism group is $S_r$ but (obviously) the number of spanning trees is 1. Alternatively, $K_r$ has the same (abstract) automorphism group and $r^{r-2}$ spanning trees. In general I think you can't say much at all. $\endgroup$
    – Brendan McKay
    Commented Sep 3, 2016 at 13:09
  • $\begingroup$ @BrendanMcKay: Thanks. Can we say anything if we impose regularity conditions, e.g. the graph is regular or strongly regular? $\endgroup$
    – Pritam Majumder
    Commented Sep 3, 2016 at 15:25
  • 1
    $\begingroup$ The usual parameters $(n,k,\lambda,\mu)$ for a strongly-regular graph determine the eigenvalues and therefore the number of spanning trees. But they don't determine the automorphism group. $\endgroup$
    – Brendan McKay
    Commented Sep 4, 2016 at 1:00

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .