On the Connectivity of Fiber Graphs

Raymond Hemmecke, Tobias Windisch

Abstract


We consider the connectivity of fiber graphs with respect to Gro ̈bner basis and Graver basis moves. First, we present a sequence of fiber graphs using moves from a Gro ̈bner basis and prove that their edge-connectivity is lowest possible and can have an arbitrarily large distance from the minimal degree. We then show that graph-theoretic properties of fiber graphs do not depend on the size of the right-hand side. This provides a counterexample to a conjecture of Engstro ̈m on the node-connectivity of fiber graphs. Our main result shows that the edge-connectivity in all fiber graphs of this counterexample is best possible if we use moves from Graver basis instead. 


Keywords


Fiber connectivity, Gro ̈bner basis, Graver basis, Fiber graph

Full Text:

PDF


DOI: http://dx.doi.org/10.18409/jas.v6i1.35

Refbacks

  • There are currently no refbacks.