✦ LIBER ✦

Spanning Planar Subgraphs of Graphs in the Torus and Klein Bottle

✍ Scribed by R. Brunet; M.N. Ellingham; Z.C. Gao; A. Metzlar; R.B. Richter

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 685 KB
Volume: 65
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1995.1041

No coin nor oath required. For personal study only.

✦ Synopsis

There are two main purposes of this article. First we show that every 3-connected graph embedded in the torus or the Klein bottle has a spanning planar subgraph which is 2-connected, and in fact has a slightly stronger connectivity property. Second, this subgraph is applied to show that every 3-connected graph that embeds in the torus or Klein bottle has both a 2-walk (a closed walk visiting every vertex exactly once or twice) and a 3-tree (a spanning tree with maximum degree at most 3). This completes the characterization of surfaces for which every embedded 3-connected graph has a 2-walk (or 3-tree). , 1995 Academic Press. Inc.

📜 SIMILAR VOLUMES

Disjoint Cycles in Directed Graphs on th

Disjoint Cycles in Directed Graphs on the Torus and the Klein Bottle

✍ G.L. Ding; A. Schrijver; P.D. Seymour 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 203 KB

We give necessary and sufficient conditions for a directed graph embedded on the torus or the Klein bottle to contain pairwise disjoint circuits, each of a given orientation and homotopy, and in a given order. For the Klein bottle, the theorem is new. For the torus, the theorem was proved before by

Chords of longest circuits of graphs emb

Chords of longest circuits of graphs embedded in torus and Klein bottle

✍ Xuechao Li; Cun-Quan Zhang 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 177 KB

## Abstract Thomassen conjectured that every longest circuit of a 3‐connected graph has a chord. It is proved in this paper that every longest circuit of a 4‐connected graph embedded in a torus or Klein bottle has a chord. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 1–23, 2003

Constructing the Graphs That Triangulate

Constructing the Graphs That Triangulate Both the Torus and the Klein Bottle

✍ Serge Lawrencenko; Seiya Negami 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 158 KB

We show how to construct all the graphs that can be embedded on both the torus and the Klein bottle as their triangulations.

Decomposition of K13 into a torus graph

Decomposition of K13 into a torus graph and a graph imbedded in the Klein bottle

✍ Oleg O. Borodin; Jean Mayer 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 86 KB

The spanning subgraphs of eulerian graph

The spanning subgraphs of eulerian graphs

✍ F. T. Boesch; C. Suffel; R. Tindell 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 312 KB

## Abstract It is shown that a connected graph __G__ spans an eulerian graph if and only if __G__ is not spanned by an odd complete bigraph __K__(2~m~ + 1, 2__n__ + 1). A disconnected graph spans an eulerian graph if and only if it is not the union of the trivial graph with a complete graph of odd

On the orientable genus of graphs embedd

On the orientable genus of graphs embedded in the klein bottle

✍ Neil Robertson; Robin Thomas 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 560 KB

## Abstract Let __G__ be a graph embedded in the Klein bottle with “representativity” at least four. We give a formula for the orientable genus of __G__, which also implies a polynomially bounded algorithm. The formula is in terms of the number of times certain closed curves on the Klein bottle int