𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Remarks on the lower bounds for the average genus

✍ Scribed by Yi-chao Chen

Publisher
Institute of Applied Mathematics, Chinese Academy of Sciences and Chinese Mathematical Society
Year
2011
Tongue
English
Weight
230 KB
Volume
27
Category
Article
ISSN
0168-9673

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Lower bounds for the average genus
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.

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

Upper and lower bounds for the average-c
Upper and lower bounds for the average-case complexity of path-search
✍ Pippenger, Nicholas πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 125 KB πŸ‘ 1 views

A channel graph is the union of all paths between a given input and a given output in an interconnection network. At any moment in time, each vertex in such a graph is either idle or busy. The search problem that we consider is to find a path (from the given input to the given output) consisting ent