Complexity of Locally Injective Homomorphism to the Theta Graphs

Abstract

A Theta graph is a multigraph which is a union of at least three internally disjoint paths that have the same two distinct end vertices. In this extended abstract we show full computational complexity characterization of the problem of deciding the existence of a locally injective homomorphism from an input graph G to any fixed Theta graph.

Keywords

• computational complexity
• locally injective homomorphism
• Theta graph