×

On random digraphs and cores. (English) Zbl 1465.05164

Summary: An acyclic homomorphism of a digraph \(C\) to a digraph \(D\) is a function \(\rho:V(C)\rightarrow V(D)\) such that for every arc \(uv\) of \(C\), either \(\rho(u)=\rho(v)\), or \(\rho(u)\rho(v)\) is an arc of \(D\) and for every vertex \(v\in V(D)\), the subdigraph of \(C\) induced by \(\rho-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\in 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, No. 18, 5535–5539 (2009; Zbl 1215.05158)] concerning random graphs and cores.

MSC:

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

Citations:

Zbl 1215.05158
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] J. Bang-Jensen and G. Gutin,Digraphs: Theory, algorithms and applications, Second edition, Springer Monographs in Mathematics, Springer-Verlag London, Ltd., London, 2009. · Zbl 1170.05002
[2] D. Bokal, G. Fijavˇz, M. Juvan, P. M. Kayll and B. Mohar, The circular chromatic number of a digraph,J. Graph Theory46(3)(2004), 227-240. · Zbl 1041.05026
[3] A. Bonato and P. Pralat, The good, the bad, and the great: homomorphisms and cores of random graphs,Discrete Math.309(18)(2009), 5535-5539. · Zbl 1215.05158
[4] J. A. Bondy and U. S. R. Murty,Graph theory, volume 244 ofGraduate Texts in Mathematics, Springer, New York, 2008. · Zbl 1134.05001
[5] P. Hell and J. Neˇsetˇril,Graphs and homomorphisms, volume 28 ofOxford Lecture Series in Mathematics and its Applications, Oxford University Press, Oxford, 2004.
[6] S. Janson, T. Luczak and A. Rucinski,Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000.
[7] E. Parsa,Aspects of uniqueD-colorability for digraphs, Thesis (Ph.D.)-University of Montana, ProQuest LLC, Ann Arbor, MI, 2019
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.