On random digraphs and cores

MaRDI QIDQ4990132zbMATH OpenFDO

Authors Esmaeil Parsa, P. Mark Kayll

Publication date 28 May 2021

Full work available at URL https://arxiv.org/abs/2101.09751, http://ajc.maths.uq.edu.au/pdf/79/ajc_v79_p371.pdf

zbMATH Keywords

acyclic homomorphismscoregraph homomorphismgreat core

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80)

Abstract: An acyclic homomorphism of a digraph $C$ to a digraph $D$ is a function $hocolonV(C)oV(D)$ such that for every arc $uv$ of $C$, either $ho(u)=ho(v)$, or $ho(u)ho(v)$ is an arc of $D$ and for every vertex $vinV(D)$, the subdigraph of $C$ induced by $h{o}^{-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 $DinD(n,p(n))$ are asymptotically almost surely cores. For digraphs, this mirrors a result from [A. Bonato and P. Pra{l}at, The good, the bad, and the great: homomorphisms and cores of random graphs, Discrete Math., 309 (2009), no. 18, 5535-5539; MR2567955] concerning random graphs and cores.

Recommendations

• The good, the bad, and the great: homomorphisms and cores of random graphs
• A construction of uniquely \(n\)-colorable digraphs with arbitrarily large digirth
• Cores and compactness of infinite directed graphs
• Multiplicativity of acyclic digraphs
• Homomorphisms of random paths

Cites work

• Digraphs
• Graph theory
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• The circular chromatic number of a digraph
• The good, the bad, and the great: homomorphisms and cores of random graphs

Cited in

(6)

• The good, the bad, and the great: homomorphisms and cores of random graphs
• Loose cores and cycles in random hypergraphs
• scientific article; zbMATH DE number 4029600 (Why is no real title available?)
• Birth of a giant \((k_{1},k_{2})\)-core in the random digraph
• Random regular graphs with edge faults: Expansion through cores
• Homomorphisms of random paths

This page was built for publication: On random digraphs and cores

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4990132)