Гомоморфизм из графа на график это отображение от в такой, что если а также смежны в тогда а также смежны в , Эндоморфизм графа является гомоморфизмом из к себе; это без фиксированной точки, если нет такой, что и это нетривиально, если это не идентичность.
Недавно я задал вопрос, связанный с автоморфизмами (и графами) множеств , то есть биективными эндоморфизмами, обратные к которым также являются эндоморфизмами. Я нашел соответствующую работу по подсчету (и определению существования) автоморфизмов, но в процессе поиска я не смог найти никаких результатов, связанных с эндоморфизмами.
Отсюда мой вопрос: в чем сложность, учитывая графикпринятия решения о существовании нетривиального эндоморфизма или подсчета количества эндоморфизмов? Тот же вопрос с эндоморфизмами без неподвижных точек.
Я думаю, что аргумент, приведенный в этом ответе, распространяется на эндоморфизмы и оправдывает то, что случай ориентированных двудольных графов или по- зетов не проще, чем проблема для общих графов (проблема для общих графов сводится к этому случаю), но его сложность не кажется простым для определения. Известно, что решение о существовании гомоморфизма от одного графа к другому является NP-трудным (это ясно, поскольку оно обобщает раскраску графа), но кажется, что ограничение поиска гомоморфизмами от графа к себе может облегчить проблему, так что это не помогает мне определить сложность этих проблем.