Paper Info
Title
On the diameter of Eulerian orientations of graphs
Abstract
We compare the diameter of a graph with the directed diameter of its Eulerian orientations. We obtain positive results under certain symmetry conditions.An Eulerian orientation of a graph is an orientation such that each vertex has the same indegree and outdegree. A graph is vertex-transitive if its vertices are equivalent under automorphisms.We show that the directed diameter of an Eulerian orientation of a finite vertex-transitive graph cannot be much larger than the undirected diameter; our bound on the directed diameter is O (dΔ ln n) where d is the undirected diameter, Δ is the (out)degree of the vertices, and n is the number of vertices. This implies that for Eulerian orientations of vertex-transitive graphs-of bounded degree, the gap between the two diameters is at most quadratic.As a consequence, we are able to compare the word length and the positive word length of elements of a finite group in terms of a given set of generators; we show that the gap is at most nearly quadratic, where the term "nearly" refers to a factor, polylogarithmic in the order of the group.It follows that recent polynomial bounds on the diameter of certain large classes of Cayley graphs of the symmetric group and certain linear groups automatically extend to directed Cayley graphs. The result also shows that the directed and undirected versions of long standing conjectures regarding the diameter of Cayley graphs of various classes of groups, including transitive permutation groups and finite simple groups, are equivalent.We also show that for edge-transitive digraphs, the directed diameter is O(d ln n).On the other hand, if we weaken the condition of vertex-transitivity to regularity (all vertices have the same degree), then the directed diameter is no longer polynomially bounded in terms of the undirected diameter and the maximum degree (and In n = O(d ln Δ)).Our upper bounds on the diameter raise the algorithmic challenge to find paths of the length guaranteed by these results. While for undirected graphs, most (but not all) relevant proofs are algorithmic, our bounds for the directed diameter are obtained via a pigeon-hole argument based on expansion and yield existence only.
Year
DOI
Venue
2006
10.1145/1109557.1109648
SODA
Keywords
Field
DocType
finite vertex-transitive graph,maximum degree,cayley graph,undirected version,undirected diameter,vertex-transitive graphs-of bounded degree,undirected graph,certain large class,ln n,eulerian orientation,upper bound,facet,face,symmetric group,permutation group,polyhedron,vertex,graph,cycle,polytope,linear inequalities
Discrete mathematics,Combinatorics,Classification of finite simple groups,Symmetric group,Vertex (geometry),Cayley graph,Permutation group,Eulerian path,Degree (graph theory),Finite group,Mathematics
Conference
ISBN
Citations
PageRank
0-89871-605-5
8
0.61
References
Authors
12
1
Name
Order
Citations
PageRank
Laszlo Babai13537573.58