zbMATH — the first resource for mathematics

The maximum genus of graphs of diameter two. (English) Zbl 0724.05021
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 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.

05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: DOI
[1] Behzad, M.; Chartrand, G.; Lesniak-Foster, L., Graphs and digraphs, (1979), Prindle, Weber and Schmidt Boston, MA · Zbl 0403.05027
[2] Jungerman, M., Characterization of upper embeddable graphs, Trans. amer. math. soc., 241, 401-406, (1978) · Zbl 0379.05025
[3] Kundu, S., Bounds on the number of disjoint spanning trees, J. combin. theory ser. B, 17, 199-203, (1974) · Zbl 0285.05113
[4] Leshchenko, V.G., One-component imbedding of graphs of one class, (), 23-26, (Russian)
[5] Nebeský, L., A new characterization of the maximum genus of a graph, Czechoslovak math. J., 31, 106, 604-613, (1981) · Zbl 0482.05034
[6] Nordhaus, E.A.; Stewart, B.M.; White, A.T., On the maximum genus of a graph, J. combin. theory ser. B, 11, 258-267, (1971) · Zbl 0217.02204
[7] Ringeisen, R.D., Survey of results on the maximum genus of a graph, J. graph theory, 3, 1-13, (1979) · Zbl 0398.05029
[8] M. Škoviera, Decay number and the maximum genus of a graph, submitted.
[9] Xuong, N.H., How to determine the maximum genus of a graph, J. combin. theory ser. B, 26, 217-225, (1979) · Zbl 0403.05035
[10] Xuong, N.H., Upper embeddable graphs and related topics, J. combin. theory ser. B, 26, 226-232, (1979) · Zbl 0403.05036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.