The proof of a conjecture of Bouabdallah and Sotteau
Min Xu, Xinmin Hou, Jun‐Ming Xu · Networks · 2004
Abstract 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−2p−1,n for 4p + 2⌈p/3⌉ + 1 ≤ n ≤ 6p, 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, … , ⌈(4p)/3⌉} can be partitioned into 2p 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−2p−1,n is equal to 5 if 4p + 2⌈p/3⌉ + 1 ≤ n ≤ 6p and to 8 if 3p + ⌈p/3⌉ + 1 ≤ n ≤ 3p + ⌈(3p)/5⌉ for any p ≥ 2. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(4), 292–296 2004