A tight lower bound on the maximum genus of a simplicial graph
Every connected simplicial graph has maximum genus at most one-half of its cycle rank [\textit{E. A. Nordhaus}, \textit{B. M. Stewart}, and the reviewer, J. Comb. Theory, Ser. B 11, 258-267 (1971; Zbl 0217.02204)]. In the present paper it is shown that such graphs having minimum valence at least three have maximum genus more than one-quarter of their cycle rank, and that this lower bound is tight. Examples of necklace multigraphs are given to show that both the simplicial and the minimum valence assumptions are essential. Applications are given to the average genus of simplicial graphs for which all vertices have valence at least three: average genus exceeds one-eighth of the cycle rank, and hence one-quarter of the maximum genus.
- A Characterization in of Upper-Embeddable Graphs
- A Kuratowski-type theorem for the maximum genus of a graph
- An additivity theorem for maximum genus of a graph
- Bounds of the number of disjoint spanning trees
- Determining all compact orientable 2-manifolds upon which \(K_{m,n}\) has 2-cell imbeddings
- Every connected, locally connected graph is upper embeddable
- Hierarchy for imbedding-distribution invariants of a graph
- How to determine the maximum genus of a graph
- scientific article; zbMATH DE number 4006288 (Why is no real title available?)
- scientific article; zbMATH DE number 3490998 (Why is no real title available?)
- scientific article; zbMATH DE number 3575611 (Why is no real title available?)
- scientific article; zbMATH DE number 3588683 (Why is no real title available?)
- scientific article; zbMATH DE number 512923 (Why is no real title available?)
- Kuratowski-type theorems for average genus
- Limit points for average genus. I: 3-connected and 2-connected simplicial graphs
- Limit points for average genus. II: 2-connected non-simplicial graphs
- Lower bounds for the average genus
- On the average genus of a graph
- On the complexity of graph embeddings
- On the maximum genus of a graph
- On the number of maximum genus embeddings of almost all graphs
- Region distributions of graph embeddings and Stirling numbers
- Region distributions of some small diameter graphs
- Survey of results on the maximum genus of a graph
- The Maximum Genus of Cartesian Products of Graphs
- The maximum genus of graphs of diameter two
- Upper-embeddable graphs and related topics
- Limit points for average genus. II: 2-connected non-simplicial graphs
- The maximum genus of graphs with diameter three
- Maximum genus and girth of graphs
- Algorithmic graph embeddings
- Maximum genus and chromatic number of graphs
- Maximum genus, girth and connectivity
- A note on the maximum genus of 3-edge-connected nonsimple graphs
- Lower bounds on the maximum genus of loopless multigraphs
- A tight lower bound on the maximum genus of a 3-connected loopless multigraph
- The maximum genus of a 3-regular simplicial graph
- A tight lower bound on the maximum genus of 3-edge connected loopless graphs
- Maximum genus and connectivity
- On the average crosscap number. II: Bounds for a graph
- Maximum genus, connectivity and minimal degree of graphs
- Cycle rank of Lyapunov graphs and the genera of manifolds
- scientific article; zbMATH DE number 1792612 (Why is no real title available?)
- Lower bounds for the average genus
- Remarks on the lower bounds for the average genus
- scientific article; zbMATH DE number 7561610 (Why is no real title available?)
- scientific article; zbMATH DE number 5583076 (Why is no real title available?)
- New bounds for the average genus and average number of faces of a simple graph
- Limit points for average genus. I: 3-connected and 2-connected simplicial graphs
- On the lower bounds for the maximum genus for simple graphs
This page was built for publication: A tight lower bound on the maximum genus of a simplicial graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1923508)
