Back to Search
Start Over
Complexity of locally-injective homomorphisms to tournaments
- Source :
- Discrete Mathematics & Theoretical Computer Science, Vol vol. 20 no. 2, Iss Graph Theory (2018)
- Publication Year :
- 2018
- Publisher :
- Discrete Mathematics & Theoretical Computer Science, 2018.
-
Abstract
- For oriented graphs $G$ and $H$, a homomorphism $f: G \rightarrow H$ is locally-injective if, for every $v \in V(G)$, it is injective when restricted to some combination of the in-neighbourhood and out-neighbourhood of $v$. Two of the possible definitions of local-injectivity are examined. In each case it is shown that the associated homomorphism problem is NP-complete when $H$ is a reflexive tournament on three or more vertices with a loop at every vertex, and solvable in polynomial time when $H$ is a reflexive tournament on two or fewer vertices.
Details
- Language :
- English
- ISSN :
- 13658050
- Volume :
- . 20
- Issue :
- Graph Theory
- Database :
- Directory of Open Access Journals
- Journal :
- Discrete Mathematics & Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- edsdoj.424b954e2ea44308a0d7c0d8951ce4f7
- Document Type :
- article
- Full Text :
- https://doi.org/10.23638/DMTCS-20-2-4