A lower bound for the connectivity of directed Euler tour transformation graphs Original Research Article

Let D be a directed Eulerian multigraph, v be a vertex of D. We call the common value of id(v) and od(v) the degree of v, and simply denote it by dv. Xia introduced the concept of the T-transformation for directed Euler tours and proved that any directed Euler tour (T)-transformation graph Eu(D) is connected. Zhang and Guo proved that Eu(D) is edge-Hamiltonian, i.e., any edge of Eu(D) is contained in a Hamilton cycle of Eu(D). In this paper, we obtain a lower bound Σ(dr−1)(dr−2)2r ϵ Q for the connectivity of Eu(D), where Q = vϵV(D)¦dv ⩾ 2. Examples are given to show that this lower bound is in some sense best possible.