✦ LIBER ✦

The cycle space of an embedded graph

✍ Scribed by B. Richter; H. Shank

Publisher: John Wiley and Sons
Year: 1984
Tongue: English
Weight: 258 KB
Volume: 8
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190080304

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let G be a connected graph with edge set E embedded in the surface ∑. Let G° denote the geometric dual of G. For a subset d of E, let τ__d__ denote the edges of G° that are dual to those edges of G in d. We prove the following generalizations of well‐known facts about graphs embedded in the plane.

(1) b is a boundary cycle in G if and only if τ__b__ is a cocycle in G°.

(2) If T is a spanning tree of G, then τ(E/T) contains a spanning tree of G°.

(3) Let T be any spanning tree of G and, for e ϵ E/T, let T(e) denote the fundamental cycle of e. Let U ∪ E/T. Then τ__U__ is a spanning tree of G° if and only if the set of face boundaries, less any one, together with the set {T(e); e ϵ E/(T ∪ U)} is a basis for the cycle space of G.

📜 SIMILAR VOLUMES

The bond and cycle spaces of an infinite

The bond and cycle spaces of an infinite graph

✍ Karel Casteels; R. Bruce Richter 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 166 KB 👁 1 views

## Abstract Bonnington and Richter defined the cycle space of an infinite graph to consist of the sets of edges of subgraphs having even degree at every vertex. Diestel and Kühn introduced a different cycle space of infinite graphs based on allowing infinite circuits. A more general point of view w

Least-Distortion Euclidean Embeddings of

Least-Distortion Euclidean Embeddings of Graphs: Products of Cycles and Expanders

✍ Nathan Linial; Avner Magen 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 139 KB

Embeddings of finite metric spaces into Euclidean space have been studied in several contexts: The local theory of Banach spaces, the design of approximation algorithms, and graph theory. The emphasis is usually on embeddings with the least possible distortion. That is, one seeks an embedding that m

Cycle systems of the line graph of the c

Cycle systems of the line graph of the complete graph

✍ Cox, B.A.; Rodger, C.A. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 562 KB

For all m = 0 (mod 41, for all n = 0 or 2 (mod m), and for all n = 1 (mod 2m) w e find an m-cycle decomposition of the line graph of the complete graph K,. In particular, this solves the existence problem when m is a power of two.

The color space of a graph

✍ Tommy R. Jensen; Carsten Thomassen 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 191 KB 👁 1 views

On the embedding of graphs into graphs w

On the embedding of graphs into graphs with few eigenvalues

✍ Vu, Van H. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 726 KB

A graph is called of type k if it is connected, regular, and has k distinct eigenvalues. For example graphs of type 2 are the complete graphs, while those of type 3 are the strongly regular graphs. We prove that for any positive integer n, every graph can be embedded in n cospectral, non-isomorphic

On the cycle-isomorphism of graphs

✍ Xingxing Yu 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 336 KB

## Abstract This paper considers conditions ensuring that cycle‐isomorphic graphs are isomorphic. Graphs of connectivity ⩾ 2 that have no loops were studied in [2] and [4]. Here we characterize all graphs __G__ of connectivity 1 such that every graph that is cycle‐isomorphic to __G__ is also isomor