A Note Concerning Equipotent Digraph Homomorphism Sets

Author(s): Allen D. Parks

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.