Remarks on homomorphisms based on Vertex Connectivity of Weighted Directed Graphs (Algebraic system, Logic, Language and Computer Science)

Abstract

We give our definition of homomorphisms(called w-homomorphisms) of general weighted directed graphs and investigate the semigroups of surjective homomorphims and synthesize graphs to obtain a generator of pricipal left (or right) ideal in the semigroup. This study is motivated by reducing the redundancy in concurrent systems, for example, Petri nets which are represented by weighted bipartite graphs. Here we can more simply obtain some results in weighted directed graphs that is generalizations of Petri nets[10]. In a general weighted directed graph, weights given to edges are mesured by some quantity, for example, usually nonnegative integers. Here slightly extending the notion of weight, we adopt and fix a kind of ring R as this quantity. For weighted digraphs (V, E_{i}, W_{i})(i=1, 2), a usual graph homomorphism $phi$ : V_{1}rightarrow V_{2} satisfies W_{2}($phi$(u), $phi$(v))=W_{1}(u, v) to preserve adjacencies of the graphs. Whereas we extend this definition slightly and our homomorphism is defined by the pair ($phi$, $rho$) based on the similarity of the edge connection. ($phi$, $rho$) satisfies W_{2}($phi$(u), $phi$(v))=$rho$(u)$rho$(v)W_{1}(u, v), where $rho$:V_{1}rightarrow Q(R) and R is a p.i.mathrm{d}. ant Q(R) is its quatient field. We investigate the semigroup S of all surjective w-homomorphisms and develop the theory of principal ideals in S. As an application, we show that some ordered sets of graphs based on surjective w-homomorphisms form lattice structures.