✦ LIBER ✦

A tight lower bound on the maximum genus of a simplicial graph

✍ Scribed by Jianer Chen; Saroja P. Kanchi; Jonathan L. Gross

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 856 KB
Volume: 156
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(95)00070-d

No coin nor oath required. For personal study only.

✦ Synopsis

It is proved that every connected simplicial graph with minimum valence at least three has maximum genus at least one-quarter of its cycle rank. This follows from the technical result that every 3-regular simplicial graph except K4 has a Xuong co-tree whose odd components have only one edge each. It is proved, furthermore, that this lower bound is tight. However, examples are used to illustrate that it does not apply to non-simplicial graphs. This result on maximum genus leads to several immediate consequences for average genus.

📜 SIMILAR VOLUMES

The Relative Maximum Genus of a Graph

✍ C.P. Bonnington 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 422 KB

Survey of results on the maximum genus o

Survey of results on the maximum genus of a graph

✍ Richard D. Ringeisen 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 619 KB

## Abstract Some of the early questions concerning the maximum genus of a graph have now been answered. In this paper we survey the progress made on such problems and present some recent results, outlining proofs for some of the major theorems.

A lower bound on the chromatic number of

A lower bound on the chromatic number of a graph

✍ B. R. Myers; R. Liu 📂 Article 📅 1971 🏛 John Wiley and Sons 🌐 English ⚖ 150 KB 👁 1 views

Lower-bounds on the connectivities of a

Lower-bounds on the connectivities of a graph

✍ Abdol H. Esfahanian 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 372 KB 👁 1 views

Lower bounds on the vulnerability of a g

Lower bounds on the vulnerability of a graph

✍ F. T. Boesch 📂 Article 📅 1972 🏛 John Wiley and Sons 🌐 English ⚖ 532 KB

Tight bounds on the chromatic sum of a c

Tight bounds on the chromatic sum of a connected graph

✍ Carsten Thomassen; Paul Erdös; Yousef Alavi; Paresh J. Malde; Allen J. Schwenk 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 236 KB 👁 1 views