Graphs whose flow polynomials have only integral roots

2009/08/03 by Joseph P. S. Kung, Gordon F. Royle, Kung, Joseph P. S. +1 · 1 citation
Mathematics · #05B35 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05B35

paper · pdf · doi:10.48550/arxiv.0908.0181

12 pages, 1 figure

arxiv created 2009/09/11 · arxiv updated 2009/12/01

Abstract

We show if the flow polynomial of a bridgeless graph G has only integral roots, then G 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.

Cited by

• Freeness of Arrangements with Regular Underlying Matroids

Related

• On graphs whose flow polynomials have real roots only
• On Zero-free Intervals of Flow Polynomials
• Zeros of Chromatic and Flow Polynomials of Graphs
• Clique Polynomials and Chordal Graphs
• Structure of the flow and Yamada polynomials of cubic graphs