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.

05C10 Planar graphs; geometric and topological aspects of graph theory
05C12 Distance in graphs
05C35 Extremal problems in graph theory