✦ LIBER ✦

The Largest Parity Demigenus of a Simple Graph

✍ Scribed by Thomas Zaslavsky

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 421 KB
Volume: 70
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1997.1766

No coin nor oath required. For personal study only.

✦ Synopsis

A graph 1 is parity embedded in a surface if a closed path in the graph is orientation preserving or reversing according as its length is even or odd. The parity demigenus of 1 is the minimum of 2&/(S) (where / is Euler characteristic) over all surfaces S in which 1 can be parity embedded. We calculate the maximum parity demigenus over all loopless graphs of order n. As a corollary we strengthen the calculation by Jungerman, Stahl, and White of the genus of K n, n with a perfect matching removed. We conclude by discussing numerous related problems.

📜 SIMILAR VOLUMES

The size of the largest hole in a random

The size of the largest hole in a random graph

✍ Tomasz Łuczak 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 775 KB

Let H(n, p) denote the size of the largest induced cycle in a random graph C(n, p). It is shown that if the expected average degree of G(n, p) is a constant larger than 1, then H(n, p) is of the order n with probability 1 -o(l). Moreover, for C(n, p) with large average degree, H(n, p) is determined

The largest induced tree in a sparse ran

The largest induced tree in a sparse random graph

✍ W. Fernandez de la Vega 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 192 KB 👁 2 views

The author proved that, for c > 1, the random graph G(n, p ) on n vertices with edge probability p = c / n contains almost always an induced tree on at least q n ( 1 -o( 1)) vertices, where L Y ~ is the positive root of the equation CLY = log( 1 + c'a). It is shown here that if c is sufficiently lar

The parity of the number of 1-factors of

The parity of the number of 1-factors of a graph

✍ Charles H.C. Little 📂 Article 📅 1972 🏛 Elsevier Science 🌐 English ⚖ 344 KB

The Order Upper Bound on Parity Embeddin

The Order Upper Bound on Parity Embedding of a Graph

✍ Thomas Zaslavsky 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 398 KB

A graph 1 is parity embedded in a surface if a closed path in the graph is orientation preserving or reversing according to whether its length is even or odd. The parity demigenus of 1 is the minimum of 2&/(S) (where / is the Euler characteristic) over all surfaces S in which 1 can be parity embedde

A functional equation for finding the la

A functional equation for finding the largest expected capacity of a graph

✍ N. G. F. Sancho 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 336 KB

On the Largest Component of the Random G

On the Largest Component of the Random Graph at a Nearcritical Stage

✍ Boris Pittel 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 225 KB

The random graphs G(n, Pr(edge)= p), G(n, \*edges=M) at the critical range p=(1+\*n &1Â3 )Ân and M=(nÂ2)(1+\*n &1Â3 ) are studied. The limiting distribution of the largest component size is determined.