Article ID Journal Published Year Pages File Type
4653953 European Journal of Combinatorics 2011 10 Pages PDF
Abstract

We show if the flow polynomial of a bridgeless graph GG has only integral roots, then GG is the dual graph to a planar chordal graph. We also show that for 3-connected cubic graphs, the same conclusion holds under the weaker hypothesis that it has only real flow roots. Expressed in the language of matroid theory, this result says that the cographic matroids with only integral characteristic roots are the cycle matroids of planar chordal graphs.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,