Enumeration of acyclic walks in a graph
type: Item
instance of: scholarly article
title: Enumeration of acyclic walks in a graph
zbMATH Open document ID: 0783.05056
DOI: 10.1016/0166-218X(93)90055-S
author: Darko Babić
author: Ante Graovac
published in: Discrete Applied Mathematics
publication date: 1993-12-07T00:00:00Z
review text: 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)\).
reviewed by: Martin Knor
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 428261
zbMATH Keywords: closed walk
zbMATH Keywords: tree
zbMATH Keywords: acyclic walks
MaRDI profile type: Publication
cites work: Q3795617
cites work: Q4552272
Recommended article: The number of walks in a graph
Recommended article: Q3077212
Recommended article: Enumeration of connected components of acyclic digraph
Recommended article: Q3822192
Recommended article: Enumeration of Hamiltonian Cycles and Paths in a Graph
Recommended article: Number of walks and degree powers in a graph
Recommended article: Q3803147
Recommended article: Q2949150
Recommended article: Counting paths in graphs
Recommended article: Q4995302
description: scientific article; zbMATH DE number 428261