On random digraphs and cores

Esmaeil Parsa, P. Mark Kayll

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)371-379
Number of pages9
JournalAustralasian Journal of Combinatorics
Volume79
StatePublished - Feb 2021

Fingerprint

Dive into the research topics of 'On random digraphs and cores'. Together they form a unique fingerprint.

Cite this