Homomorphically Full Oriented Graphs
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 orientat...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2023-10-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | http://dmtcs.episciences.org/9957/pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849344640959905792 |
|---|---|
| author | Thomas Bellitto Christopher Duffy Gary MacGillivray |
| author_facet | Thomas Bellitto Christopher Duffy Gary MacGillivray |
| author_sort | Thomas Bellitto |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-65c0f1e5d3ef4ead88f5c8acc30719a2 |
| institution | Kabale University |
| issn | 1365-8050 |
| language | English |
| publishDate | 2023-10-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj-art-65c0f1e5d3ef4ead88f5c8acc30719a22025-08-20T03:42:37ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502023-10-01vol. 25:2Graph Theory10.46298/dmtcs.99579957Homomorphically Full Oriented GraphsThomas BellittoChristopher Duffyhttps://orcid.org/0000-0003-1657-3172Gary MacGillivrayHomomorphically 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.http://dmtcs.episciences.org/9957/pdfcomputer science - discrete mathematicsmathematics - combinatorics05c60, 05c20, 68q17 |
| spellingShingle | Thomas Bellitto Christopher Duffy Gary MacGillivray Homomorphically Full Oriented Graphs Discrete Mathematics & Theoretical Computer Science computer science - discrete mathematics mathematics - combinatorics 05c60, 05c20, 68q17 |
| title | Homomorphically Full Oriented Graphs |
| title_full | Homomorphically Full Oriented Graphs |
| title_fullStr | Homomorphically Full Oriented Graphs |
| title_full_unstemmed | Homomorphically Full Oriented Graphs |
| title_short | Homomorphically Full Oriented Graphs |
| title_sort | homomorphically full oriented graphs |
| topic | computer science - discrete mathematics mathematics - combinatorics 05c60, 05c20, 68q17 |
| url | http://dmtcs.episciences.org/9957/pdf |
| work_keys_str_mv | AT thomasbellitto homomorphicallyfullorientedgraphs AT christopherduffy homomorphicallyfullorientedgraphs AT garymacgillivray homomorphicallyfullorientedgraphs |