This paper shows that in the undirected binary de Bruijn graph of dimension n, UB(n), which has diameter n, there exist at least two internally vertex disjoint paths of length at most n between any two vertices. In other words, the 2-diameter of UB(n) is equal to its diameter n. © 1996 John Wiley & Sons, Inc.

A spanning subgraph $G'$ of a simple undirected graph G is a t-spanner of G if every pair of vertices that are adjacent in G are at distance at most t in $G'$. The parameter t is called the dilation of the spanner. Spanners with small dilations have many applications, such as their use as low-cost approximations of communication networks with only small degradations in performance. In this paper, we derive spanners with small dilations for four closely related bounded-degree approximations of hypercubes: butterflies, cube-connected cycles, binary de Bruijn graphs, and shuffle-exchange graphs. We give both direct constructions and methods for deriving spanners for one class of graphs from spanners for another class. We prove that most of our spanners are minimum in the sense that spanners with fewer edges have larger dilations.

Let n be an integer and F={f/sub 1/:1/spl les/i/spl les/t for some integer t} be a finite set of linear functions. We define a linear congruential graph G(F, n) as a graph on the vertex set V={0, 1, ..., n-1}, in which any x/spl isin/V is adjacent to f/sub i/(x) mod n, 1/spl les/i/spl les/t. For a linear function g, and a subset V/sub 1/ of V we define a linear congruential graph G(F, n, g,V/sub 1/) as a graph on vertex set V, in which any x/spl isin/V is adjacent to f/sub i/(x) mod n, 1/spl les/i/spl les/t, and any x/spl isin/V/sub 1/ is also adjacent to g(x) mod n. These graphs generalize several well known families of graphs, e.g. the de Bruijn graphs. We give a family of linear functions, called DCC linear functions, that generate regular, highly connected graphs which are of substantially larger order than de Bruijn graphs of the same degree and diameter. Some theoretical and empirical properties of these graphs are given and their structural properties are studied.

Abstract For a given connected graph G of order n, a routing R is a set of n(n ‐ 1) simple paths R(x, y) specified for every ordered pair (x, y) of vertices in G. A routing R is consistent if for every vertex z on R(x, y) the paths R(x, z) and R(z, y) are induced by R(x, y). A network is defined by an ordered pair (G, R), where G is a connected graph and R is a routing of G. The vertex‐forwarding index ζ(G, R) of a network (G, R) is the maximum number of paths of R passing through any vertex of G. The minimum of ζ(G, R) over all possible routings of a connected graph G is denoted by ζ(G). Similarly, the notion of the edge‐forwarding index of a network can be defined. In this paper, we prove that, in general, the vertex‐forwarding index cannot be obtained by taking the minimum of ζ(G, R) over all possible consistent routings of G. However, this can be done for the class of Cayley graphs. We prove for a specific class of routings that the computation of ζ(G) is NP‐complete for graphs of diameter at least 4 and is polynomial for graphs of diameter 2. Similar problems are studied for the edge‐forwarding index. © 1994 John Wiley & Sons, Inc.

Abstract For a given graph G of order n, a routing R is a set of n(n − 1) elementary paths specified for every ordered pair of vertices in G. The edge forwarding index of a network (G,R), denoted π(G,R) is the maximum number of paths of R going through any edge e of G. The edge forwarding index of G, denoted π(G), is the minimum of π(G,R) taken over all the possible routings R of G. Given n ≤ 15 and Δ ≤ n − 1 we determine πΔ,n, the minimum of π(G) taken over all graphs G of order n with maximum degree at most Δ. This is known as the edge forwarding index problem. © 1993 by John Wiley & Sons, Inc.