A Note Concerning Equipotent Digraph Homomorphism Sets

A Note Concerning Equipotent Digraph Homomorphism Sets

Loading document ...
Loading page ...


Author(s): Allen D. Parks

Download Full PDF Read Complete Article

DOI: 10.18483/ijSci.2017 7 41 47-52 Volume 8 - May 2019


Functor adjunctions are fundamental to category theory and have recently found applications in the empirical sciences. In this paper a functor adjunction on a special full subcategory of the category of digraphs is borrowed from mathematical biology and used to equate cardinalities of sets of homomorphisms between various types of digraphs and associated line digraphs. These equalities are especially useful for regular digraphs and are applied to obtain homomorphism set cardinality equalities for the classes of de Bruijn digraphs and Kautz digraphs. Such digraphs play important roles in bioinformatics and serve as architectures for distributed high performance computing networks.


Category Theory, Functors, Adjunctions, Digraphs, Line Digraphs, Homomorphisms, De Bruijn Digraphs, Kautz Digraphs


  1. Döring, A., Isham, C. J. A topos foundation for theories of physics: I. Formal languages for physics. Journal of Mathematical Physics, 2008, vol. 49, 053515, DOI:10.1063/1.2883740.
  2. Döring, A., Isham, C. J. A topos foundation for theories of physics: II. Daseinisation and the liberation of quantum theory. Journal of Mathematical Physics, 2008, vol. 49, 053516, DOI:10.1063/1.2883742.
  3. Döring, A., Isham, C. J. A topos foundation for theories of physics: III. The representation of physical theories with arrows δ ̆^O (A): Σ→R^≿. Journal of Mathematical Physics, 2008, vol. 49, 053517, DOI:10.1063/1.2883777.
  4. Döring, A., Isham, C. A topos foundation for theories of physics: IV. Categories of systems. Journal of Mathematical Physics, 2008, vol. 49, 053518, DOI:10.1063/1.2883836.
  5. Wiels,V., Easterbrook, S. Management of evolving specifications using category theory. In: Proceedings of the 13th IEEE International Conference on Automated Systems Engineering. 1998, p. 12-21.
  6. Gebreyohannes, S., Edmonson, W., Esterline, A. Formalization of the Responsive and Formal Design Process using Category Theory. In: Systems Conference (SysCon), 2018 Annual IEEE International, IEEE. 2018, p. 1-8.
  7. Kokar, M., Tomasik, J., Weyman, J. Data vs. decision fusion in the category theory framework. FUSION 2001, 2001.
  8. Barr, M., Wells, C. Category Theory for Computing Science. Prentice Hall, New York, 2002.
  9. Pavlovic, D. Tracing the man in the middle of monoidal categories. arXiv:1203.6324 [cs:LO], 2012.
  10. Andrian, J., Kamhoua, C., Kiat, K., Njilla, L. Cyber Threat Information Sharing: A Category-Theoretic Approach. In: Third International Conference on Mobile and Secure Services (MobiSecServ), IEEE. 2017, p. 1-5.
  11. Mabrok, M., Ryan, M. Category Theory as a Formal Mathematical Foundation for Model-Based Systems Engineering. Appl. Math. Inf. Sci., 2017, Vol. 11, p. 43-51, DOI: 10.18576/amis/110106.
  12. Wisnesky, R., Breiner, S., Jones, A., Spivak, D., Subrahmanian, E. Using Category Theory to Facilitate Multiple Manufacturing Service Database Integration. J. Comput. Inf. Sci. Eng., 2017, Vol. 17, 021011, DOI: 10.1115/1.4034268.
  13. Rudskiy, I. arXiv:1702.04627v1 [q-bio.TO], 2017.
  14. Phillips, S. A General (Category Theory) Principle for General Intelligence: Duality (Adjointness). In: Artificial General Intelligence. AGI 2017. Everitt, T., Goertzel, B., Potapov, A. Eds. Lecture Notes in Computer Science, Vol. 10414; Springer, Cham, DOI: 10.1007/978-3-319-63703-7 6.
  15. Haruna, T., Gunji, Y-P. Duality between decomposition and gluing: A theoretical biology via adjoint functors. Biosystems, 2007, vol. 90, 716-727.
  16. Haruna, T., Gunji, Y-P. An Algebraic Description of Development of Hierarchy. International Journal of Computing Anticipatory Systems, 2008, vol. 20, 131-143.
  17. Zerbina, D., Birney, E. Velvet: Algorithms for de novo short read assembly using de Bruijn graphs. Genome Research, published in advance in March 2008, DOI: 10.1101/gr.074492.107.
  18. Tvrdik, P., Harbane, R., Heydemann, M-C. Uniform homomorphisms of de Bruijn and Kautz networks. Discrete Applied Mathematics, 1998, vol. 83, 279-301.
  19. Hell, P., Nešetřil, J. Graphs and Homomorphisms. Oxford University Press Inc., New York, 2004.

Cite this Article:

  • BibTex
  • RIS
  • APA
  • Harvard
  • IEEE
  • MLA
  • Vancouver
  • Chicago

International Journal of Sciences is Open Access Journal.
This article is licensed under a Creative Commons Attribution 4.0 International (CC BY 4.0) License.
Author(s) retain the copyrights of this article, though, publication rights are with Alkhaer Publications.

Search Articles

Issue May 2019

Volume 8, May 2019

Table of Contents

Order Print Copy

World-wide Delivery is FREE

Share this Issue with Friends:

Submit your Paper