On the universal Gr?bner bases of toric ideals of graphs

摘要

The universal Gr?bner basis of an ideal is a Gr?bner basis with respect to all term orders simultaneously. We characterize in graph theoretical terms the elements of the universal Gr?bner basis of the toric ideal of a graph. We also provide a new degree bound. Finally, we give examples of graphs for which the true degrees of their circuits are less than the degrees of some elements of the Graver basis.