Lattices of surjective weak weight preserving homomorphisms of digraphs (Developments of Language, Logic, Algebraic system and Computer Science)

Abstract

We introduced an extension of homomorphisms of general weighted directed graphs and investigated the semigroups of surjective homomorphims and synthesize graphs to obtain a generator of pricipal left (or right) ideal in the semigroup[11]. This study is originally motivated by reducing the redundancy in concurrent systems, for example, Petri nets. [10]. We have got the result that for a given graph our homomorphism G has freeness determined by the connection and the cycles in G. In a general weighted directed graphs (V_{i}, 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 adjacency 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 mathrm{t}V_{2}($phi$(u), $phi$(v)) = $rho$(u) $rho$(v)W_{1}(u, v), where $phi$ : V_{1} rightarrow V_{2}, $rho$ : V_{1} rightarrow R+ and R_{+} is the set of positive real numbers. In this paper we investigate whether for a mathrm{w}-homomorphism ($phi$, $rho$) from a given digraph G, $rho$ is uniquely determined or not. As a result, it is uniquely determined if undirected graph overline{G} obtained from G has no even cycles and no isolated vertices. Additionally we overview the lattice structure of graphs, which are ordered by surjective w-homomorphisms.