A Note onk-Connected Rayless Graphs

✍ Scribed by Rudolf Halin

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 160 KB
• Volume: 72
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1997.1795

✦ Synopsis

In this note a short new proof of Diestel's characterization theorem for infinite k-connected rayless graphs is given, using the concept of the order of a rayless graph which was introduced by R. Schmidt.

1998 Academic Press Diestel [3, Theorem 4.3] gives a beautiful description of the structure of rayless k-connected graphs, showing that they decompose into finite k-connected graphs in a treelike manner. Based on Schmidt's concept of order of a rayless graph , in this note a new and short proof of Diestel's theorem is given; the present author thus hopes to contribute a step toward a unified theory of rayless graphs.

Diestel's aforementioned result reads exactly as follows.

Theorem I. For every graph G the following two statements are equivalent:

(a) G is rayless and k-connected;

(b) G has a rayless k-connected tree decomposition into finite k-connected parts.

Here, k is any positive integer; a graph is rayless if it contains no infinite path; a tree-decomposition is rayless if its decomposition tree is rayless, and it is k-connected if adjacent parts overlap in at least k vertices.

More formally, condition (b) is equivalent (see [1, Chap. I]) to the existence of a well-ordered family F=(B * ) * # _ (where _ is an ordinal) of k-connected finite induced subgraphs of G such that the following conditions (1) (4) are satisfied.