Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653953 | European Journal of Combinatorics | 2011 | 10 Pages |
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
Joseph P.S. Kung, Gordon F. Royle,