论文标题
同型完全取向图
Homomorphically Full Oriented Graphs
论文作者
论文摘要
同态完整图是每个同构图像对子图的同构。我们以两种不同的方式扩展了同型填充的定义到定向图。对于其中的第一个，我们表明同派完全取向图作为同源图的准传递方向。反过来，这为这些同型完全取向的图提供了有效的识别和构造算法。对于第二个，我们表明相关的识别问题是胃肠道，并且确定图表是否允许同源性完全方向的问题是NP完整的。在这样做时，我们表明了确定两个给定的定向簇是否是同构的问题。
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.
