Constructing goal-minimally k-diametric graphs by lifts

An undirected graph G with diameter k is said to be goal-minimally k-diametric if for every edge uv of G, the inequality dG−uv(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 ofk-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).