Can I read Formulas Counting Spanning Trees in Line Graphs and Their Extensions on EtoBox?

Formulas Counting Spanning Trees in Line Graphs and Their Extensions by Dong, Fengming is a scholarly article available to read on EtoBox.

What is Formulas Counting Spanning Trees in Line Graphs and Their Extensions about?

For any connected multigraph $G=(V,E)$ and any $M\subseteq E$, if $M$ induces an acyclic subgraph of $G$ and removing all edges in $M$ yields a subgraph of $G$ whose components are complete graphs, a formula for $\tau_G(M)$ is obtained, where $\tau_G(M)$ is the number of spanning trees in $G$ which contain all edges in $M$. Applying this result, we can easily obtain a formula for the number of spanning trees in the line graph or the middle graph of an arbitrary graph. Applying this result, we also show that for any connected graph $G$ with a clique $U$ which is a cut-set of $G$, the number of spanning trees in $G$ has a factorization which is analogous to a property of the chromatic polynomial of $G$.

Author

Dong, Fengming

Published

2019

Language

EN