You are here

On the Connectivity of Fiber Graphs

Journal Name:

Publication Year:

Author NameUniversity of Author
Abstract (2. Language): 
We consider the connectivity of ber graphs with respect to Grobner basis and Graver basis moves. First, we present a sequence of ber graphs using moves from a Grobner 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 ber graphs do not depend on the size of the right-hand side. This provides a counterexample to a conjecture of Engstrom on the node-connectivity of ber graphs. Our main result shows that the edge-connectivity in all ber graphs of this counterexample is best possible if we use moves from Graver basis instead.
24
45