# zbMATH — the first resource for mathematics

The maximum genus of diameter three graphs. (English) Zbl 0862.05027
Let $$G$$ be a connected multigraph of order $$p$$ and size $$q$$, and let $$\gamma_M (G)$$ be the maximum genus of $$G$$. The Betti deficiency of $$G$$ is defined to be $$q-p + 1-2 \gamma_M(G)$$. The authors study the maximum genus parameter for graphs of diameter at least 3, proving that the Betti deficiency of a multigraph with diameter 3 is at most 2. This compares to a result of M. Škoviera [Discrete Math. 87, No. 2, 175-180 (1991; Zbl 0724.05021)] that a multigraph with diameter 2 is upper embeddable (i.e. has Betti deficiency at most 1). A characterization is given of diameter 3 simple graphs having Betti deficiency 2. Thus the maximum genus is determined, for all simple graphs of diameter 3.

##### MSC:
 05C10 Planar graphs; geometric and topological aspects of graph theory 05C12 Distance in graphs 05C35 Extremal problems in graph theory
##### Keywords:
multigraph; genus; Betti deficiency; diameter