Networks communicating for each pairing of terminals

Let G be a multigraph of maximum degree Δ and with a set of t vertices of degree one, called terminals. We call G a (Δ, t)‐network if for any pairing of its terminals there exist edge‐disjoint paths in G between those pairs (t is even). The concept of (Δ, t)‐networks is introduced to model the situation when switching processors having Δ ports are to be connected in such a way that simultaneous communication is possible for any pairing of the free ports. We establish some properties of (Δ, t)‐networks. In particular, we investigate optimal (or near‐optimal) networks and obtain lower and upper bounds on the function n(Δ, t), the minimum number of interior nodes a (Δ, t)‐network can have.