TY - JOUR
T1 - On random digraphs and cores
AU - Parsa, Esmaeil
AU - Kayll, P. Mark
N1 - Publisher Copyright:
© The author(s). Released under the CC BY-ND 4.0 International License.
PY - 2021/2
Y1 - 2021/2
N2 - An acyclic homomorphism of a digraph C to a digraph D is a function ρ: V (C) → V (D) such that for every arc uv of C, either ρ(u) = ρ(v), or ρ(u)ρ(v) is an arc of D and for every vertex v ε V (D), the subdigraph of C induced by ρ-1(v) is acyclic. A digraph D is a core if the only acyclic homomorphisms of D to itself are automorphisms. In this paper, we prove that for certain choices of p(n), random digraphs D ε D(n, p(n)) are asymptotically almost surely cores. For digraphs, this mirrors a result from [A. Bonato and P. Prałat, Discrete Math. 309 (18) (2009), 5535- 5539; MR2567955] concerning random graphs and cores.
AB - An acyclic homomorphism of a digraph C to a digraph D is a function ρ: V (C) → V (D) such that for every arc uv of C, either ρ(u) = ρ(v), or ρ(u)ρ(v) is an arc of D and for every vertex v ε V (D), the subdigraph of C induced by ρ-1(v) is acyclic. A digraph D is a core if the only acyclic homomorphisms of D to itself are automorphisms. In this paper, we prove that for certain choices of p(n), random digraphs D ε D(n, p(n)) are asymptotically almost surely cores. For digraphs, this mirrors a result from [A. Bonato and P. Prałat, Discrete Math. 309 (18) (2009), 5535- 5539; MR2567955] concerning random graphs and cores.
UR - http://www.scopus.com/inward/record.url?scp=85100912723&partnerID=8YFLogxK
M3 - Article
AN - SCOPUS:85100912723
SN - 1034-4942
VL - 79
SP - 371
EP - 379
JO - Australasian Journal of Combinatorics
JF - Australasian Journal of Combinatorics
ER -