𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The Genus Problem for Cubic Graphs

✍ Scribed by Carsten Thomassen

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
206 KB
Volume
69
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

We prove that the following problem is NP-complete: Given a cubic graph G and a natural number g, is it possible to draw G on the sphere with g handles added?

πŸ“œ SIMILAR VOLUMES

Face Covers and the Genus Problem for Ap
Face Covers and the Genus Problem for Apex Graphs
✍ Bojan Mohar πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 198 KB

A graph G is an apex graph if it contains a vertex w such that G&w is a planar graph. It is easy to see that the genus g(G) of the apex graph G is bounded above by {&1, where { is the minimum face cover of the neighbors of w, taken over all planar embeddings of G&w. The main result of this paper is

The Solution of a Problem of Godsil on C
The Solution of a Problem of Godsil on Cubic Cayley Graphs
✍ Cai Heng Li πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 267 KB

In this short paper, we give a positive answer to a question of C. D. Godsil (1983, Europ. J. Combin. 4, 25 32) regarding automorphisms of cubic Cayley graphs of 2-groups: ``If Cay(G, S) is a cubic Cayley graph of a 2-group G and A=Aut Cay(G, S), does A 1 {1 imply Aut(G, S){1?'' 1998 Academic Press

On the max-cut problem for a planar, cub
On the max-cut problem for a planar, cubic, triangle-free graph, and the Chinese postman problem for a planar triangulation
✍ Carsten Thomassen πŸ“‚ Article πŸ“… 2006 πŸ› John Wiley and Sons 🌐 English βš– 109 KB πŸ‘ 2 views

## Abstract Every 3‐connected planar, cubic, triangle‐free graph with __n__ vertices has a bipartite subgraph with at least 29__n__/24β€‰βˆ’β€‰7/6 edges. The constant 29/24 improves the previously best known constant 6/5 which was considered best possible because of the graph of the dodecahedron. Example

The spectrum problem for the Petersen gr
The spectrum problem for the Petersen graph
✍ Adams, Peter; Bryant, Darryn E. πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 305 KB πŸ‘ 2 views

It is shown that there exists a decomposition of K,, into edge-disjoint copies of the Petersen graph if and only if 'u = 1 or 10 (mod 151, 'u # 10.