A tight lower bound on the maximum genus of a simplicial graph (Q1923508): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
Property / author | |||
Property / author: Jian'er Chen / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Arthur T. White / rank | |||
Normal rank |
Revision as of 23:09, 19 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A tight lower bound on the maximum genus of a simplicial graph |
scientific article |
Statements
A tight lower bound on the maximum genus of a simplicial graph (English)
0 references
5 January 1997
0 references
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.
0 references
maximum genus
0 references
cycle rank
0 references
minimum valence
0 references
simplicial graphs
0 references