Concatenation and Multiplication of directed graphs of a special class

Abstract

On the set of oriented graphs with exactly one sink and exactly one source, two binary operations are considered. Concatenation identifies the sink of the first digraph with the source of the second, while multiplication replaces all arcs of the first digraph with the second digraph, identifying the source with the start of an arc and the sink with the end. The set of studied graphs is closed under these two operations, and the collection of oriented paths with concatenation and multiplication operations forms a semiring isomorphic to the semiring of natural numbers. The paper analyzes previous works in the field of oriented graphs, particularly results related to the applied use of the studied class of graphs as models of transport networks. .The obtained theoretical results on the properties of the new operations and the descriptions of the kings of the resulting digraphs provide a foundation for further research, the development of generalizations, and the modeling of more complex systems for applied problems.