Constructing goal-minimally -diametric graphs by lifts

An undirected graph G with diameter k is said to be goal-minimally k -diametric if for every edge u v of G , the inequality d G − u v ( x , y ) > k holds if and only if { x , y } = { u , v } . It is rather difficult to construct such graphs, especially for odd diameters. In this paper we construct an infinite family with diameter 5. This family is the first non-trivial infinite family of k -GMD graphs for odd k . We also show how one can construct some known infinite families of various diameters. Further, we give the first examples of such graphs with diameters 9 and 13. All these graphs were constructed by lifts (voltage assignments).