
arXiv: 2208.10727
Homomorphically full graphs are those for which every homomorphic image is isomorphic to a subgraph. We extend the definition of homomorphically full to oriented graphs in two different ways. For the first of these, we show that homomorphically full oriented graphs arise as quasi-transitive orientations of homomorphically full graphs. This in turn yields an efficient recognition and construction algorithms for these homomorphically full oriented graphs. For the second one, we show that the related recognition problem is GI-hard, and that the problem of deciding if a graph admits a homomorphically full orientation is NP-complete. In doing so we show the problem of deciding if two given oriented cliques are isomorphic is GI-complete.
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), mathematics - combinatorics, directed graph homomorphism, Directed graphs (digraphs), tournaments, 05c60, 05c20, 68q17, computer science - discrete mathematics, 05C60, 05C20, 68Q17, QA1-939, Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.), FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), complexity, Mathematics, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), mathematics - combinatorics, directed graph homomorphism, Directed graphs (digraphs), tournaments, 05c60, 05c20, 68q17, computer science - discrete mathematics, 05C60, 05C20, 68Q17, QA1-939, Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.), FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), complexity, Mathematics, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
