Peter Knorr: Disjoint paths spanning simple polytopal graphs, p.145-150

Abstract:

In this paper, the definition of traceability is extended to n-path-traceability, i. e. the existence of a spanning set of n disjoint paths. Subsequently, an algorithm is provided to show that for each natural number $n > 1$, there is a simple 3-polytopal graph with at most 44n + 46 vertices which is not n-path-traceable

Key Words: Spanning subgraphs, spanning set of paths, simple 3-polytopes.

2000 Mathematics Subject Classification: Primary: 05C38.

Download the paper in pdf format here.