Geodesic
Homomorphically Full Oriented Graphs
Discrete mathematics & theoretical computer science, Tome 25 (2023-2024) no. 2.

Voir la notice de l'article provenant de la source Episciences

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.
DOI : 10.46298/dmtcs.9957
Classification : 05C20, 05C60 
@article{DMTCS_2024_25_2_a4,
     author = {Bellitto, Thomas and Duffy, Christopher and MacGillivray, Gary},
     title = {Homomorphically {Full} {Oriented} {Graphs}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {25},
     number = {2},
     year = {2023-2024},
     doi = {10.46298/dmtcs.9957},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.9957/}
}
TY  - JOUR
AU  - Bellitto, Thomas
AU  - Duffy, Christopher
AU  - MacGillivray, Gary
TI  - Homomorphically Full Oriented Graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2023-2024
VL  - 25
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.9957/
DO  - 10.46298/dmtcs.9957
LA  - en
ID  - DMTCS_2024_25_2_a4
ER  - 
%0 Journal Article
%A Bellitto, Thomas
%A Duffy, Christopher
%A MacGillivray, Gary
%T Homomorphically Full Oriented Graphs
%J Discrete mathematics & theoretical computer science
%D 2023-2024
%V 25
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.9957/
%R 10.46298/dmtcs.9957
%G en
%F DMTCS_2024_25_2_a4
Bellitto, Thomas; Duffy, Christopher; MacGillivray, Gary. Homomorphically Full Oriented Graphs. Discrete mathematics & theoretical computer science, Tome 25 (2023-2024) no. 2. doi : 10.46298/dmtcs.9957. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.9957/

Cité par Sources :