✦ LIBER ✦

Maximum Genus, Girth and Connectivity

✍ Scribed by Deming Li; Yanpei Liu

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 88 KB
Volume: 21
Category: Article
ISSN: 0195-6698
DOI: 10.1006/eujc.1999.0398

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, the lower bounds of maximum genera of simplicial graphs under the constraints of girth and connectivity are discussed extensively. A complete picture on the lower bounds of maximum genera of graphs is formed. There are infinitely many graphs with the maximum genera attaining these lower bounds.

📜 SIMILAR VOLUMES

The maximum valency of regular graphs wi

The maximum valency of regular graphs with given order and odd girth

✍ Guo-Hui Zhang 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 294 KB 👁 1 views

## Abstract The odd girth of a graph __G__ is the length of a shortest odd cycle in __G__. Let __d__(__n, g__) denote the largest __k__ such that there exists a __k__‐regular graph of order __n__ and odd girth __g__. It is shown that __d____n, g__ ≥ 2|__n__/__g__≥ if __n__ ≥ 2__g__. As a consequenc

The maximum interval number of graphs wi

The maximum interval number of graphs with given genus

✍ Edward R. Scheinerman 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 202 KB 👁 1 views

The interval number of a graph G, denoted i(G), is the least positive integer t such that G is the intersection graph of sets, each of which is the union of t compact real intervals. It is known that every planar graph has interval number at most 3 and that this result is best possible. We investiga

Maximum matchings in a regular graph of

Maximum matchings in a regular graph of specified connectivity and bounded order

✍ P. Katerinis 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 213 KB

Face Size and the Maximum Genus of a Gra

Face Size and the Maximum Genus of a Graph 1. Simple Graphs

✍ Yuanqiu Huang; Yanpei Liu 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 150 KB

This paper shows that a simple graph which can be cellularly embedded on some closed surface in such a way that the size of each face does not exceed 7 is upper embeddable. This settles one of two conjectures posed by Nedela and S8 koviera (1990, in ``Topics in Combinatorics and Graph Theory,'' pp.

Constructing a bipartite graph of maximu

Constructing a bipartite graph of maximum connectivity with prescribed degrees

✍ Asano, Takao 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 328 KB 👁 3 views

d 2,n 2 ) is a bipartite graphical sequence, if there is a bipartite graph G with degrees {D 1 , D 2 } (i.e., G has two independent vertex sets In other words, {D 1 , D 2 } is a bipartite graphical sequence if and only if there is an n 1 1 n 2 matrix of 0's and 1's having d 1j 1 1's in row j 1 and

Convex Programming and Circumference of

Convex Programming and Circumference of 3-Connected Graphs of Low Genus

✍ Zhicheng Gao; Xingxing Yu 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 376 KB