Home » Subject » Graph Theory » Algebraic G.T.
Importance: Medium ✭✭
Author(s): Mohar, Bojan
Subject: Graph Theory
» Algebraic Graph Theory
Keywords: nowhere-zero flow
Recomm. for undergrads: no
Posted by: mohar
on: May 31st, 2007

Let $ \Phi(G,x) $ be the flow polynomial of a graph $ G $. So for every positive integer $ k $, the value $ \Phi(G,k) $ equals the number of nowhere-zero $ k $-flows in $ G $.

Conjecture   $ \Phi(G,5.5) > 0 $ for every 2-edge-connected graph $ G $.

By Seymour's 6-flow theorem, $ \Phi(G,k) > 0 $ for every 2-edge-connected graph $ G $ and every integer $ k\ge6 $.

It would be interesting to find any non-integer rational number $ x>5 $ so that $ \Phi(G,x) > 0 $ for every 2-edge-connected graph $ G $. It is known that zeros of flow polynomials are dense in the complex plane.

Bibliography



* indicates original appearance(s) of problem.
add new comment

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options