# Is a given graph a k-trail?

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

(suggested by András Sebő)

# Problem Statement

A k-tree is a tree whose degrees are bounded by k, and a k-trail of a graph is the homomorphic image of a (freely chosen) k-tree onto the vertex set of a graph, where edges are counted with multiplicity.

Question: Can it be decided in polynomial time if a given multigraph is a k-trail (where the multiplicities of the homomorphism must coincide with those of the multigraph)? For fixed k? For k=3?

# What is known?

For k=2 the problem is polynomially solvable, since it is equivalent to the existence of an Eulerian trail with possibly a starting point different from the endpoint. Every graph contains a 2-trail, since doubling the edges of an odd join (T-join, where T is the set of odd degree vertices) we get a 2-trail. (If the multiplicities are at most 1 this is NP-hard though. If they are at least one, this is a Chinese postman problem and can be minimized for arbitrary weights.) However, the minimum cardinality 2-trail problem is NP-hard, since it contains the Hamiltonicity of cubic graphs.