On enumeration of spanning subgraphs with a preassigned cyclomatic number in a graph (Q1207353)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On enumeration of spanning subgraphs with a preassigned cyclomatic number in a graph |
scientific article |
Statements
On enumeration of spanning subgraphs with a preassigned cyclomatic number in a graph (English)
0 references
1 April 1993
0 references
Let \(G\) be a labelled undirected graph with no loops but with parallel edges allowed (multigraph), and let \(\sigma_ n(G)\) be the number of connected spanning subgraphs of \(G\) with cyclomatic number (number of edges -- number of vertices +1) equal to \(n\). Choose any pair of vertices which are joined by \(m\geq 1\) edges, and let \(\hat eG\) (respectively, \(\dot eG)\) be the graph obtained from \(G\) by deleting (respectively, contracting) all the edges joining these two vertices. The following recursive formula is stated, and a special case of it is derived: \[ \sigma_ n(G)=\sigma_ n(\hat eG)+\sum^{n+1}_{i=1}{m\choose n+2- i}\sigma_{i-1}(\dot eG). \] This generalizes the non-recursive formulae given in \textit{C. J. Liu} and \textit{Y. Chow} [Enumeration of connected spanning subgraphs of a planar graph, Acta Math. Hung. 41, 27-36 (1983; Zbl 0517.05044)] for \(\sigma_ n(G)\), where \(G\) is a planar graph, and in \textit{G. Kirchhoff} [Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird, Ann. Phys. Chem. 72, 497-508 (1847)] for \(\sigma_ 0(G)\), where \(G\) is an arbitrary graph. Reviewer's remarks: In the formula in the paper, the vertices are assumed to be the ones with the highest labels, but if these are not adjacent the formula reads \(\sigma_ n(G)=\sigma_ n(G)\). The letter \(\chi\), which usually means chromatic number, is used for the cyclomatic number instead of the usual letter \(\nu\). No reference is given to Kirchhoff's paper or any other source of this formula. And the examples cannot be followed without first reading the aforementioned paper of C. J. Liu and the author.
0 references
enumeration
0 references
multigraph
0 references
spanning subgraphs
0 references
cyclomatic number
0 references
recursive formula
0 references
chromatic number
0 references