The maximum genus of graphs of diameter two
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.
- A Characterization in of Upper-Embeddable Graphs
- A new characterization of the maximum genus of a graph
- Bounds of the number of disjoint spanning trees
- How to determine the maximum genus of a graph
- scientific article; zbMATH DE number 3625415 (Why is no real title available?)
- On the maximum genus of a graph
- Survey of results on the maximum genus of a graph
- Upper-embeddable graphs and related topics
- Up-embeddability via girth and the degree-sum of adjacent vertices
- Upper embeddability of graphs
- The maximum genus of graphs with diameter three
- Maximum genus and chromatic number of graphs
- Face size and the maximum genus of a graph. I: Simple graphs
- A tight lower bound on the maximum genus of a simplicial graph
- Exponentially many genus embeddings of the complete graph \(K_{12s+3}\)
- Maximum genus, connectivity and minimal degree of graphs
- On the maximum order of graphs embedded in surfaces
- scientific article; zbMATH DE number 4177080 (Why is no real title available?)
- Minimum genus embeddings of the complete graph
- scientific article; zbMATH DE number 97632 (Why is no real title available?)
- scientific article; zbMATH DE number 907923 (Why is no real title available?)
- Extremal graphs of diameter two and given maximum degree, embeddable in a fixed surface
- scientific article; zbMATH DE number 969182 (Why is no real title available?)
- scientific article; zbMATH DE number 5583076 (Why is no real title available?)
- A note on the maximum genus of graphs with diameter 4
- scientific article; zbMATH DE number 2230287 (Why is no real title available?)
- scientific article; zbMATH DE number 2230288 (Why is no real title available?)
- Upper embeddability of graphs and products of transpositions associated with edges
- A sufficient condition on upper embeddability of graphs
This page was built for publication: The maximum genus of graphs of diameter two
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2276970)
