Locally Injective Homomorphism to the Simple Weight Graphs

Abstrakt

A Weight graph is a connected (multi)graph with two vertices u and v of degree at least three and other vertices of degree two. Moreover, if any of these two vertices is removed, the remaining graph contains a cycle.

A Weight graph is called simple if the degree of u and v is three. 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 simple Weight graph by identifying some polynomial cases and some NP-complete cases.

Klíčová slova

• computational complexity
• locally injective homomorphism
• Weight graph