✦ LIBER ✦

On the average genus of the random graph

✍ Scribed by Saul Stahl

Publisher: John Wiley and Sons
Year: 1995
Tongue: English
Weight: 640 KB
Volume: 20
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190200102

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We obtain an upper bound on the expected number of regions in the randomly chosen orientable embedding of a fixed graph. This bound is ised to show that the average genus of the random graph on v vertices is close to its maximum genus. More specifically, it is proven that the difference between these two parameters is bounded by a function that is linear in v. These bounds are obtained in the context of permutation—partition pairs. © 1996 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

Bounds for the average genus of the vert

Bounds for the average genus of the vertex-amalgamation of graphs

✍ Saul Stahl 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 628 KB

The average orientable genus of graphs has been the subject of a considerable number of recent investigations. It is the purpose of this article to examine the extent to which the average genus of the amalgamation of graphs fails to be additive over its constituent subgraphs. This discrepancy is bou

On the Spectral Radius and the Genus of

On the Spectral Radius and the Genus of Graphs

✍ H. Yuan 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 205 KB

In this paper, we obtain a relation between the spectral radius and the genus of a graph. In particular, we give upper bounds on the spectral radius of graphs with \(n\) vertices and small genus. " " 1995 Academic Press. Ins

Lower bounds for the average genus

✍ Jianer Chen; Jonathan L. Gross; Robert G. Rieper 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 705 KB

Two lower bounds are obtained for the average genus of graphs. The average genus for a graph of maximum valence at most 3 is at least half its maximum genus, and the average genus for a 2-connected simplicial graph other than a cycle is at least 1/16 of its cycle rank.

On the genus and connectivity of Hamilto

On the genus and connectivity of Hamiltonian graphs

✍ Richard A. Duke 📂 Article 📅 1972 🏛 Elsevier Science 🌐 English ⚖ 675 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.

On genus imbeddings of the tensor produc

On genus imbeddings of the tensor product of graphs

✍ Abay-Asmerom, Ghidewon 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 566 KB

In this article new genus results for the tensor product H @ G are presented. The second factor G in H @ G is a Cayley graph. The imbedding technique used to establish these results combines surgery and voltage graph theory. This technique was first used by A. T. White [171. This imbedding technique