Endomorphisms of undirected modifications of directed graphs (Q1201251): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 07:04, 31 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Endomorphisms of undirected modifications of directed graphs |
scientific article |
Statements
Endomorphisms of undirected modifications of directed graphs (English)
0 references
17 January 1993
0 references
Let a directed graph \(H=(V,A)\) without loops be given, i.e., \(V\) is an arbitrary set, \(A\subseteq V\times V\) and never \((a,a)\in A\). There are two standard ways how to create an undirected graph from it, namely to create its reflection (its upper modification) \[ {\mathcal R} H=(V,E_{\mathcal R})\quad\text{with}\quad\{v,w\}\in E_{\mathcal R}\quad\text{iff}\quad (v,w)\in A\cup A^{-1} \] and its coreflection (= lower modification) \[ {\mathcal C} H=(V,H_{\mathcal C})\quad\text{with}\quad \{v,w\}\in E_{\mathcal C}\quad\text{iff}\quad (v,w)\in A\cap A^{-1}. \] If \(\tau\) is an automorphism (or an endomorphism) of \(H\), then it is also an automorphism (or an endomorphism) of \({\mathcal R} H\) and of \({\mathcal C} H\). Hence the automorphism group \(\Aut H\) is a subgroup of \(\Aut{\mathcal R} H\) and of \(\Aut{\mathcal C} H\). Is there an other relation between the groups \(\Aut H\), \(\Aut{\mathcal R}H\) and \(\Aut{\mathcal C} H\)? More in detail, which spans of groups, where \(m_ 1\), \(m_ 2\) are monomorphisms, can be realized by directed graphs \(H\)? In the present paper, we prove the following. Theorem 1. Every span of groups can be realized by a directed graph. What we really prove here is the following. Proposition. Let \(M\) be a monoid, let \(M_ 1\), \(M_ 2\) be its submonoids and \(M_ 0=M_ 1\cap M_ 2\). Then there exist a directed graph \(H\) and isomorphisms \(\varphi_ 1\) of \(M_ 1\) onto the endomorphism monoid \(\text{End }{\mathcal R} H\) and \(\varphi_ 2\) of \(M_ 2\) onto \(\text{End }{\mathcal C} H\) which coincide on \(M_ 0\) and their joint restriction is an isomorphism of \(M_ 0\) onto \(\text{End } H\). The theorem is an immediate consequence of the proposition.
0 references
directed graph
0 references
reflection
0 references
coreflection
0 references
automorphism group
0 references
monoid
0 references
isomorphisms
0 references
endomorphism
0 references