Originators: Aradhana Narula Tam and Philip J. Lin (presented by Jennifer Wise - REGS 2010)
Definitions: A graph is k-trail-ordered if any list v0,&hellip,vk of k+1 distinct vertices can be visited in order by a trail (i.e., a walk with no repeated edges). The visits to these vertices need not be immediately consecutive on the trail. Similarly, a graph is k-circuit-ordered if any list v1,&hellip,vk of k distinct vertices can be visited in order by a circuit (i.e., a closed trail).
Background: This problem arose in the context of a wavelength assignment problem in a WDM optical network. In the desired trail or circuit, each vi may appear repeatedly, as long as somewhere in the ordered list of vertices along the trail or circuit the listed vertices appear in that order.
Question 1: Is every k-edge-connected graph also k-trail-ordered? If not, then what is the least value f(k) such that every f(k)-edge-connected graph is k-trail-ordered?
Comments: Whitney's Theorem on edge-disjoint paths yields f(2)=2, as desired. In [NLM] it was proved that f(3)=3. Pfender observed that a result of Okamura [O] implies that f(k)=k when k is even, and consequently f(k) ≤ k+1 when k is odd. Therefore, it remains to decide between k and k+1 when k is odd. Since adding a twin of a vertex does not reduce the edge-connectivity, any edge-connectivity that guarantees k-trail-ordered also guarantees k-circuit-ordered. For odd k, perhaps it is easier to prove the weaker result that k-edge-connected graphs are k-circuit-ordered than to show that f(k)=k.
Question 2: Does being k-trail-ordered imply being k-circuit-ordered? Or vice-versa, excluding complete graphs?
Comments: A stronger condition than k-circuit-ordered is k-ordered, in which the circuit for a list of k vertices is required to be a cycle (no repeated vertices); k-ordered graphs were introduced by Ng and Schultz and studied extensively in [FFGJL]. Every (k+1)-ordered graph is k-trail-ordered, but the connectivity condition guaranteeing a (k+1)-ordered graph is stronger than needed for k-trail-ordered graphs. For example, the square of the 8-cycle (adding the chords of length 2) is 4-connected but not 4-ordered. Perhaps analogues of other sufficient conditions for the k-ordered property hold for k-trail-ordered or k-circuit-ordered.
A yet stronger condition, implying all those above, is weakly k-linked, which requires that for every list s1,…,sk, t1,…,tk ∈ V(G), there exist edge-disjoint paths P1,…Pn such that Pi has endpoints si and ti for each i. Let g(k) be the least integer such that every g(k)-edge-connected graph is weakly k-linked. Thomassen [T] proved that g(k) is well defined and proved the lower bounds for his conjecture below:
Conjecture 3 (Thomassen): g(k)=k when k is odd, and g(k)=k+1 when k is even.
Comments: Okamura [O] proved that g(k)≤3k/2 and later that g(k)≤6k/5. Huck [H] proved that g(k) exceeds the value conjectured by Thomassen by at most 1. Hence Question 1 asks whether the threshold is just a bit smaller for the weaker property of being k-trail-ordered. Huck's result is another way to conclude f(k)≤k+1 when k is odd.
Question 4: What graphs are k-trail-ordered (or k-circuit-ordered) but not weakly-k-linked?
References:
[FFGJL] J.R. Faudree, R.J. Faudree, R.J. Gould, M.S. Jacobson, L. Lesniak, On
k-ordered graphs, J. Graph Theory 35 (2000) 69-82.
[H] Huck, Andreas;
A sufficient condition for graphs to be weakly k-linked.
Graphs Combin. 7 (1991), no. 4, 323.351.
[NLM] A. Narula-Tam, P. J. Lin, E. Modiano, Efficient routing and wavelength
assignment for reconfigurable WDM networks, IEEE J. Selected Areas Comm. 20
(2002) 75-88.
[O] H. Okamura, Paths in k-edge-connected graphs, J. Combin. Theory Ser.
B 45 (1988) 345-355.
[T] Thomassen, Carsten; 2-linked graphs.
European J. Combin. 1 (1980), no. 4, 371--378.