Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This is an old question of Aradhana Narula-Tam and Philip Lin that I think deserves wider circulation. It appeared in Discrete Math. 257 (2002), page 613, but not many people have looked at it and it might have a simple solution.

A graph is $k$-trail-ordered if for every list $v_0, \ldots, v_k$ of $k + 1$ distinct vertices, there is a trail (i.e., a walk with no repeated edges) that visits $v_0, \ldots, v_k$ in order (among a possibly longer trail). The question is, is every $k$-edge-connected graph also $k$-trail-ordered? If not, then what is the least edge-connectivity $f(k)$ such that every $f(k)$-edge-connected graph is $k$-trail-ordered?

Note that in the desired trail, each $v_i$ may appear repeatedly, as long as the list of vertices visited has $v_0, \ldots, v_k$ as a sublist in order. The problem arose in the context of a wavelength assignment problem in a WDM optical network. Whitney’s Theorem on edge-disjoint paths yields $f(2)=2$, as desired. In [1] it was proved that $f(3)=3$. Florian Pfender points out that a result of Okamura [2] yields a proof that $f(k)=k$ when $k$ is even, and consequently $f(k) \le k + 1$ when $k$ is odd. Therefore, it remains to decide between $k$ and $k + 1$ when $k$ is odd.

[1] 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.

[2] H. Okamura, Paths in $k$-edge-connected graphs, J. Combin. Theory Ser. B 45 (1988) 345–355.

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.