TY - JOUR

T1 - On random digraphs and cores

AU - Parsa, Esmaeil

AU - Kayll, P. Mark

N1 - Funding Information:
∗ Partially supported by a grant from the Simons Foundation (#279367 to Mark Kayll), and partially supported by a 2017 University of Montana Graduate Student Summer Research Award funded by the George and Dorothy Bryan Endowment. This work forms part of the author’s PhD dissertation [7]. † Partially supported by a grant from the Simons Foundation (#279367 to Mark Kayll).
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 -