✦ LIBER ✦

Maximum genus and girth of graphs

✍ Scribed by Yuangqiu Huang

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 302 KB
Volume: 194
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(98)00152-6

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, a lower bound on the maximum genus of a graph in terms of its girth is established as follows: let G be a simple graph with minimum degree at least three, and let g be the girth of G. Then ?M(G)~> ~fl(G) + 1 except for G=K4, g-1 where ]~(G) denotes the cycle rank of G and K4 is the complete graph with four vertices.

📜 SIMILAR VOLUMES

Maximum Genus, Girth and Connectivity

✍ Deming Li; Yanpei Liu 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 88 KB

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 low

Graphs of given genus and arbitrarily la

Graphs of given genus and arbitrarily large maximum genus

✍ Richard D. Ringeisen 📂 Article 📅 1973 🏛 Elsevier Science 🌐 English ⚖ 540 KB

Abstrart. The maximum genus of a connected graph (: is the maximum among the genera of a!1 cornpact olientable 2-manifolds upon which G has 2-&l embeddings. In the theorems that fc-llow the use of an edg;:-adding techniq se is combined with ihe well-known Edmonds' technique to prfiruce the desired r

Maximum genus and chromatic number of gr

Maximum genus and chromatic number of graphs

✍ Yuanqiu Huang 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 157 KB

Let T be a spanning tree of a connected graph G. Denote by (G; T ) the number of components in G\E(T ) with odd number of edges. The value minT (G; T ) is known as the Betti deÿciency of G, denoted by (G), where the minimum is taken over all spanning trees T of G. It is known (N.H. Xuong, J. Combin.

The maximum genus of vertex-transitive g

The maximum genus of vertex-transitive graphs

✍ Martin Škoviera; Roman Nedela 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 911 KB

The maximum genus of all vertex-transitive graphs is computed. It is proved that a k-valent vertex-transitive graph of girth g is upper-embeddable whenever k 3 4 or g 2 4. Non-upper-embeddable vertex-transitive graphs are characterized. A particular attention is paid to Cayley graphs. Groups for wh

The Relative Maximum Genus of a Graph

✍ C.P. Bonnington 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 422 KB

On the maximum genus of a graph

✍ E.A Nordhaus; B.M Stewart; A.T White 📂 Article 📅 1971 🏛 Elsevier Science 🌐 English ⚖ 415 KB