Paper Info
Title
Sums Of Squares And Negative Correlation For Spanning Forests Of Series Parallel Graphs
Abstract
We provide new evidence that spanning forests of graphs satisfy the same negative correlation properties as spanning trees, derived from Lord Rayleigh's monotonicity property for electrical networks. The main result of this paper is that the Rayleigh difference for the spanning forest generating polynomial of a series parallel graph can be expressed as a certain positive sum of monomials times squares of polynomials. We also show that every regular matroid is independent-set-Rayleigh if and only if every basis-Rayleigh binary matroid is also independent-set-Rayleigh.
Year
Venue
Keywords
2012
AUSTRALASIAN JOURNAL OF COMBINATORICS
spanning tree,sum of squares,independent set,electrical network,satisfiability
Field
DocType
Volume
Discrete mathematics,Combinatorics,Minimum degree spanning tree,Polynomial,Series-parallel graph,Spanning tree,Connected dominating set,Regular matroid,Monomial,Mathematics,Minimum spanning tree
Journal
52
ISSN
Citations 
PageRank 
2202-3518
0
0.34
References 
Authors
6
1
Name
Order
Citations
PageRank
Alejandro Erickson1145.84