The maximum genus of graphs of diameter two (Q2276970)

The maximum genus \(\gamma_ M(G)\) of a finite connected graph G is the largest genus among all closed orientable 2-manifolds in which G has a 2- cell imbedding. If \(\gamma_ M(G)\) attains the Euler upper bound of \((| E(G)| -| V(G)| +1)/2,\) G is said to be upper- imbeddable. In this paper, G is assumed to be finite, connected, and of diameter two. If, in addition, G has no loops, then it is shown to be upper imbeddable. If G has loops, it is shown that \(\gamma_ M(G)\) is at most 2 away from its Euler upper bound, if G is 2-connected; the exact value of \(\gamma_ M(G)\) is computed, if G has connectivity 1. (Throughout the discussion, G is allowed to have multiple edges.) The main result generalizes work of \textit{V. G. Leshchenko} [Properties of graphs of certain classes (Russian), Akad. Nauk Ukr. SSR, Inst. Mat., Kiev, 23-26 (1981)], who showed that every simple graph of diameter two with even Betti number is upper imbeddable.