Extensions of networks with given diameter

AbstractThis article deals with combinatorial problems motivated by the design of large interconnection networks, in particular how to extend a network by adding nodes while keeping the degree and diameter small. We consider D-admissible extensions in which nodes are added one by one while the diameter remains constant. A D-admissible extension from a graph G to a graph G' is a sequence of graphs G = G0, G1,..., Gi,..., Gk = G', where Gi is a subgraph of Gi+1, ¦V(Gi+1)¦ = ¦V(Gi)¦ + 1 and all of the Gi have diameter at most D. Furthermore we insist that some of the Gi are among the largest of the known graphs with maximum degree and diameter constant. We show that there exist D-admissible extensions from the hypercube of degree d to the hypercube of degree d + 1. Then we study D-admissible extension from the de Bruijn graph UB(d, D) [resp. Kautz graph UK(d, D)] of maximum degree 2d and diameter D to UB(d + 1, D) [resp. UK(d + 1, D)], and show that such D-admissible extensions exist if D = 2, but do not exist if D>2 and d>4