Enumeration of acyclic walks in a graph (Q686419)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Enumeration of acyclic walks in a graph |
scientific article |
Statements
Enumeration of acyclic walks in a graph (English)
0 references
7 December 1993
0 references
Acyclic walk of a graph is a closed walk whose projection is a tree. Let \(S\) be a subtree of \(G\). Denote by \(v_ 1,\ldots,v_{t_ S}\) those vertices of \(G-S\) which are adjacent with vertices of \(S\) in \(G\). Let \(g_ i\) denote the number of vertices of \(S\) adjacent with \(v_ i\), \(1 \leq i \leq t_ S\). Let \(\omega_ \ell(G)\) and \(\omega_ \ell^{ac}(G)\) denote the number of closed and acyclic walks of \(G\), respectively, with length \(\ell\). It is shown that \(\omega_ \ell^{ac}(G)=\sum_ Sm(S)\cdot \omega_ \ell(S)\), where \(S\) goes over all subtrees of \(G\), and \(m(S)=\prod^{t_ S}_{i=1}(1-g_ i)\).
0 references
closed walk
0 references
tree
0 references
acyclic walks
0 references