Decomposition of infinite eulerian graphs with a small number of vertices of infinite degree (Q1331972)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Decomposition of infinite eulerian graphs with a small number of vertices of infinite degree |
scientific article |
Statements
Decomposition of infinite eulerian graphs with a small number of vertices of infinite degree (English)
0 references
26 January 1995
0 references
Let \(G_ n\) be an infinite eulerian graph (i.e., graph whose vertices are of even or infinite degree) that has exactly \(n\) vertices of infinite degree, and only finitely many finite components after the removal of the vertices of infinite degree. Is it possible to decompose \(G_ n\) into edge disjoint (finite or infinite) circuits and rays (one-way infinite paths)? As shown by Sabidussi, the answer is positive if \(n \leq 2\). On the other hand, Thomassen gave an example showing that such a decomposition does not exist if \(n>4\). In the paper it is proved that the answer is affirmative if \(n=3\).
0 references
locally finite graph
0 references
eulerian graph
0 references
circuits
0 references
rays
0 references
decomposition
0 references