✦ LIBER ✦

Lower bounds for the average genus

✍ Scribed by Jianer Chen; Jonathan L. Gross; Robert G. Rieper

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

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 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

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

Lower bounds for lower Ramsey numbers

✍ Ralph Faudree; Ronald J. Gould; Michael S. Jacobson; Linda Lesniak 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 310 KB 👁 1 views

## Abstract For any graph __G__, let __i__(__G__) and μ;(__G__) denote the smallest number of vertices in a maximal independent set and maximal clique, respectively. For positive integers __m__ and __n__, the lower Ramsey number __s__(__m, n__) is the largest integer __p__ so that every graph of or

Lower Bounds for Shellsort

✍ C.Greg Plaxton; Torsten Suel 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 226 KB

We show lower bounds on the worst-case complexity of Shellsort. In particular, Ž Ž 2 . Ž . 2 . we give a fairly simple proof of an ⍀ n lg n r lg lg n lower bound for the size of Shellsort sorting networks for arbitrary increment sequences. We also show an identical lower bound for the running time o

Average Costs of a Graph Exploration: Up

Average Costs of a Graph Exploration: Upper and Lower Bounds

✍ Nicola Galli 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 168 KB

We consider the exploration of random digraphs. We give upper and lower bounds for the expected number of edges traversed during an exploration. This result implies a lower bound for the expected running time of a wide class of algorithms, e.g., breadth-first-search, depth-first-search, and algorith

Bounds for the Genus of Space Curves

✍ Valentina Beorchia 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 537 KB

## Abstract We compute the following upper bounds for the maximal arithmetic genus __P~a~(d,t__) over all locally Cohen ‐ Macaulay space curves of degree __d__, which are not contained in a surface of degree magnified image These bounds are sharp for t ≤ 4 abd any d ≥ t.