A tight lower bound on the maximum genus of a 3-connected loopless multigraph (Q1595254): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1007/s11766-000-0032-5 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2011639612 / rank | |||
Normal rank | |||
Revision as of 21:24, 19 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A tight lower bound on the maximum genus of a 3-connected loopless multigraph |
scientific article |
Statements
A tight lower bound on the maximum genus of a 3-connected loopless multigraph (English)
0 references
11 February 2001
0 references
Let \(B(G)\) denote the cycle rank of a graph \(G\). The authors show that every 3-connected loopless multigraph \(G\) with \(B(G)< 10\) is upper-imbeddable; if \(B(G)\geq 10\), then the maximum genus of \(G\) is at least \(B(G)/3+ 1\). The lower bound is tight: there are infinitely many 3-connected loopless multigraphs attaining this bound.
0 references
loopless multigraph
0 references
maximum genus
0 references
lower bound
0 references
