Skip to content

Graphs with integer flow roots

September 11, 2009

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
No comments yet

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: