Decomposition of infinite eulerian graphs with a small number of vertices of infinite degree

DOI10.1016/0012-365X(92)00524-UMaRDI QIDQ1331972zbMATH OpenFDO

Authors François Laviolette

Publication date 26 January 1995

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(92)00524-U

zbMATH Keywords

circuitsdecompositioneulerian graphlocally finite graphrays

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

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\).

Recommendations

• Decompositions of infinite graphs. II: Circuit decompositions
• Decompositions of infinite graphs. I: Bond-faithful decompositions
• On Hamilton decompositions of infinite circulant graphs
• scientific article; zbMATH DE number 3865323
• A decomposition of locally finite graphs

Cites work

• scientific article; zbMATH DE number 3833989 (Why is no real title available?)
• Infinite Euler Graphs

Cited in

(5)

• Quasiray decomposition of infinite graphs
• Decompositions of infinite graphs. I: Bond-faithful decompositions
• Decompositions of infinite graphs. II: Circuit decompositions
• Decomposition of Graphs into Chains
• ÜBER Euler‐Linien Unendlicher Graphen

This page was built for publication: Decomposition of infinite eulerian graphs with a small number of vertices of infinite degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1331972)