✦ LIBER ✦

Fixed-edge theorem for graphs with loops

✍ Scribed by Richard Nowakowski; Ivan Rival

Publisher: John Wiley and Sons
Year: 1979
Tongue: English
Weight: 521 KB
Volume: 3
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190030404

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let G be an undirected graph without multiple edges and with a loop at every vertex—the set of edges of G corresponds to a reflexive and symmetric binary relation on its set of vertices. Then every edge‐preserving map of the set of vertices of G to itself fixes an edge [{f(a), f(b)} = {a, b} for some edge (a, b) of G] if and only if (i) G is connected, (ii) G contains no cycles, and (iii) G contains no infinte paths. The proof is conerned with those subgraphs H of a graph G for which there is an edge‐preserving map f of the set of vertices of G onto the set of vertices of H and satisfying f(a) = a for each vertex a of H.

📜 SIMILAR VOLUMES

A fixed cube theorem for median graphs

✍ Hans-Jürgen Bandelt; Marcel van de Vel 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 513 KB

The following result is proven: every edge-preserving self-map of a median graph leaves a cube invariant. This extends a fixed edge theorem for trees and parallels a result on invariant simplices in contractible graphs.

On the fixed edge of planar graphs with

On the fixed edge of planar graphs with minimum degree five

✍ Baogang Xu; Hongbing Fan 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 207 KB

An edge e of a finite and simple graph G is called a fixed edge of G if G -e + e' ~G implies e' = e. In this paper, we show that planar graphs with minimum degree 5 contain fixed edges, from which we prove that a class of planar graphs with minimum degree one is edge reconstructible.

A six-color theorem for the edge-face co

A six-color theorem for the edge-face coloring of plane graphs

✍ Cuiqin Lin; Guanzhang Hu; Zhongfu Zhang 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 218 KB

It was shown (Kronk and Mitchen, 1973) that the set of vertices, edges and faces of any normal map on the sphere can be colored with seven colors. In this paper we solve a somewhat different problem: the set of edges and faces of any plane graph with A ~< 3 can be colored by six colors.

Menger's theorem for infinite graphs wit

Menger's theorem for infinite graphs with ends

✍ Henning Bruhn; Reinhard Diestel; Maya Stein 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB

## Abstract A well‐known conjecture of Erdős states that given an infinite graph __G__ and sets __A__, ⊆ __V__(__G__), there exists a family of disjoint __A__ − __B__ paths 𝓅 together with an __A__ − __B__ separator __X__ consisting of a choice of one vertex from each path in 𝓅. There is a natural

Linear arboricity for graphs with multip

Linear arboricity for graphs with multiple edges

✍ Houria Aït-djafer 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 266 KB

Akiyama, Exoo, and Harary conjectured that for any simple graph G with maximum degree A(G). the linear arboricity / a ( G ) satisfies rA(G)/21 5 /a(G) 5 r(A(G) + 11/21, Here it is proved that if G is a loopless graph with maximum degree A ( G ) S k and maximum edge multiplicity ## 1. Introduction

Fixed point theorems for mappings with l

Fixed point theorems for mappings with lipschitzian iterates

✍ Jarosław Górnicki; Manfred Krüppel 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 554 KB