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.
翻译：完全正态图形是每个正态图像都具有正态图象的图象。 我们以两种不同的方式将正态整形图象的定义扩展至方向图象。 首先,我们显示全态整形图象作为全态整形图象的准临时方向而出现。 这反过来又为这些全态整形图图象提供了有效的识别和构建算法。 第二,我们显示相关的识别问题是GI硬的,而决定一个图形是否接受全态整形图的问题则是NP的完整。 因此,我们显示了决定两个正态的圆形图象是否为GI的不完整问题。
相关内容
微信扫码咨询专知VIP会员