Extensions of networks with given diameter (Q1123211)

The paper is motivated by some problems in the design of large interconnection networks. A D-admissible extension from a graph G to a graph \(G'\) is a sequence of graphs \(G=G_ 0,G_ 1,...,G_ k=G'\) such that \(G_ i\) is an induced subgraph of \(G_{i+1}\), \(| V(G_{i+1})| =| V(G_ i)| +1\) and all the \(G_ i\) have diameters at most D. There are constructed D-admissible extensions between hypercubes (from degree d to \(d+1\) and between de Bruijn networks.