Article ID Journal Published Year Pages File Type
420620 Discrete Applied Mathematics 2008 7 Pages PDF
Abstract

By use of elementary geometric arguments we prove the existence of a special integral solution of a certain system of linear equations. The existence of such a solution then yields the NP-hardness of the decision problem on the existence of locally injective homomorphisms to Theta graphs with three distinct odd path lengths.

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
On the computational complexity of partial covers of Theta graphs
Authors
, , ,