Monographs, a Category of Graph Structures

Abstract : Does a graph necessarily have nodes? May an edge be adjacent to itself and be a self-loop? These questions arise in the study of graph structures, i.e., monadic many-sorted signatures and the corresponding algebras. A simple notion of monograph is proposed that generalizes the standard notion of directed graph and can be drawn consistently with them. It is shown that monadic many-sorted signatures can be represented by monographs, and that the corresponding algebras are isomorphic to the monographs typed by the corresponding signature monograph. Monographs therefore provide a simple unifying framework for working with monadic algebras. Their simplicity is illustrated by deducing some of their categorial properties from those of sets.