Premium
The proof of a conjecture of Bouabdallah and Sotteau
Author(s) -
Xu Min,
Hou Xinmin,
Xu JunMing
Publication year - 2004
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20041
Subject(s) - combinatorics , conjecture , mathematics , graph , order (exchange) , set (abstract data type) , discrete mathematics , enhanced data rates for gsm evolution , connectivity , computer science , telecommunications , finance , economics , programming language
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