Counting unbranched subgraphs

DOI10.1023/A:1018690328814MaRDI QIDQ1283455zbMATH OpenFDO

Authors David Ruelle

Publication date 23 June 1999

Published in Journal of Algebraic Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/A:1018690328814

zbMATH Keywords

counting polynomialunbranched subgraph

Mathematics Subject Classification ID

Enumeration in graph theory (05C30)

Review text

For a given graph \(G=(V,E)\), its unbranched subgraph is defined to be an edge-induced spanning subgraph such that the degree of each vertex is not greater than 2. The main result shows that the real part of any root of the polynomial \[ Q(z)=\sum_{F}z^{| F| }, \] where \(F\) is taken over all the subsets of \(E\) such that \(F\) forms an unbranched subgraph of \(G\), is always negative.

Recommendations

• Graph-counting polynomials for oriented graphs
• Zeros of graph-counting polynomials
• On the roots of the subtree polynomial
• Almost unimodal and real-rooted graph polynomials

Cites work

• Multipartition Series
• Statistical Theory of Equations of State and Phase Transitions. II. Lattice Gas and Ising Model
• Theorems on the Partition Functions of the Heisenberg Ferromagnets
• Theory of monomer-dimer systems

Cited in

(12)

• Weighted enumeration of spanning subgraphs with degree constraints
• Counting unlabeled structures
• Zeros of graph-counting polynomials
• Graph-counting polynomials for oriented graphs
• Zero-freeness and approximation of real Boolean Holant problems
• Central limit theorems, Lee-Yang zeros, and graph-counting polynomials
• Weighted enumeration of spanning subgraphs in locally tree-like graphs
• Location of the Lee-Yang zeros and absence of phase transitions in some Ising spin systems
• The Lee‐Yang and Pólya‐Schur programs. II. Theory of stable polynomials and applications
• Approximating real-rooted and stable polynomials, with combinatorial applications
• About David Ruelle, after his 80th birthday
• The complexity of ferromagnetic 2-spin systems on bounded degree graphs

This page was built for publication: Counting unbranched subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1283455)