Graphs with integer flow roots

I’ve just uploaded a new version of a paper on graphs with integer flow roots to the arxiv. This is a joint paper with the matroid theorist Joe Kung from University of North Texas.

It is basically a dual version of the old problem of characterising graphs whose chromatic polynomials have integer roots. Chordal graphs, which are built up from a single vertex by repeatedly adding a new vertex adjacent to a clique, are one such class of graphs. But there are lots of non-chordal examples, and it seems hopeless to try and classify them all.

We considered the dual problem of the graphs whose flow polynomials have integer roots. Again there is an obvious class of examples, namely the planar duals of chordal graphs, but in this case there are no other examples. So the punchline of our paper is that “the obvious examples are the only examples”.

In matroid terms, the result says that a cographic matroid with integer characteristic roots is necessarily supersolvable.

We needed the new version because a student at MIT, Maria Monks, spotted a (fixable) error in the first version. This was despite the paper having been refereed and accepted already! So the power of the arxiv has saved Joe and I some red faces.

Advertisements

Up ↑