𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The maximum genus of graphs of diameter two

✍ Scribed by Martin Škoviera

Publisher
Elsevier Science
Year
1991
Tongue
English
Weight
400 KB
Volume
87
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Skoviera, M., The maximum genus of graphs of diameter two, Discrete Mathematics 87 (1991) 175-180. Let G be a (finite) graph of diameter two. We prove that if G is loopless then it is upper embeddable, i.e. the maximum genus y,&G) equals [fi(G)/Z], where /3(G) = IF(G)1 -IV(G)1 + 1 is the Betti number of G. For graphs with loops we show that [p(G)/21 -2s yM(G) c &G)/Z] if G is vertex 2-connected, and compute the exact value of yM(G) if the vertex-connectivity of G is 1. We note that by a result of Jungerman [2] and Xuong [lo] 4-connected graphs are upper embeddable. Theorem 1. Every loopless graph of diameter two is upper embeddable.

📜 SIMILAR VOLUMES

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

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 degree in graphs of diameter 2
Maximum degree in graphs of diameter 2
✍ Paul Erdös; Siemion Fajtlowicz; Alan J. Hoffman 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 163 KB
Maximum pebbling number of graphs of dia
Maximum pebbling number of graphs of diameter three
✍ Boris Bukh 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 93 KB 👁 1 views

## Abstract Given a configuration of pebbles on the vertices of a graph __G__, a __pebbling move__ consists of taking two pebbles off some vertex __v__ and putting one of them back on a vertex adjacent to __v__. A graph is called __pebbleable__ if for each vertex __v__ there is a sequence of pebbli