Endomorphisms of undirected modifications of directed graphs (Q1201251): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Symmetric relations (undirected graphs) with given semigroups / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4074924 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Homomorphisms of graphs and of their orientations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5840024 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On symmetric and antisymmetric relations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3208855 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3788036 / rank | |||
Normal rank |
Revision as of 13:03, 17 May 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