The proof of a conjecture of Bouabdallah and Sotteau

Let G be a connected graph of order n . A routing in G is a set of n ( n − 1) fixed paths for all ordered pairs of vertices of G . The edge‐forwarding index of G , π( G ), is the minimum of the maximum number of paths specified by a routing passing through any edge of G taken over all routings in G , and π Δ, n is the minimum of π( G ) taken over all graphs of order n with maximum degree at most Δ. To determine π n −2 p −1, n for 4 p + 2⌈ p /3⌉ + 1 ≤ n ≤ 6 p , A. Bouabdallah and D. Sotteau proposed the following conjecture in [On the edge forwarding index problem for small graphs, Networks 23 (1993), 249–255]. The set 3 × {1, 2, … , ⌈(4 p )/3⌉} can be partitioned into 2 p pairs plus singletons such that the set of differences of the pairs is the set 2 × {1, 2, … , p }. This article gives a proof of this conjecture and determines that π n −2 p −1, n is equal to 5 if 4 p + 2⌈ p /3⌉ + 1 ≤ n ≤ 6 p and to 8 if 3 p + ⌈ p /3⌉ + 1 ≤ n ≤ 3 p + ⌈(3 p )/5⌉ for any p ≥ 2. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(4), 292–296 2004