Thomas Bellitto ; Christopher Duffy ; Gary MacGillivray - Homomorphically Full Oriented Graphs

dmtcs:9957 - Discrete Mathematics & Theoretical Computer Science, October 2, 2023, vol. 25:2 - https://doi.org/10.46298/dmtcs.9957
Homomorphically Full Oriented GraphsArticle

Authors: Thomas Bellitto ; Christopher Duffy ; Gary MacGillivray

    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.


    Volume: vol. 25:2
    Section: Graph Theory
    Published on: October 2, 2023
    Accepted on: August 11, 2023
    Submitted on: August 24, 2022
    Keywords: Computer Science - Discrete Mathematics,Mathematics - Combinatorics,05C60, 05C20, 68Q17
    Funding:
      Source : OpenAIRE Graph
    • Funder: Natural Sciences and Engineering Research Council of Canada

    Consultation statistics

    This page has been seen 345 times.
    This article's PDF has been downloaded 219 times.