Note on directed proper connection number of a random graph

Ran Gu, Bo Deng and Rui Li

Applied Mathematics and Computation, 2019, vol. 361, issue C, 169-174

Abstract: For an arc-colored digraph D, we say D is properly strongly connected, if for any ordered pair of vertices (x, y), D contains a directed path from x to y such that any adjacent arcs in that path have distinct colors. The directed proper connection number pc→(D) of a digraph D, is the minimum number of colors to make D properly strongly connected. Let D(n, p) denote the random digraph model, in which every arc of a digraph is chosen with probability p independently from other arcs. We prove that if p={logn+loglogn+λ(n)}/n, then with high probability, pc→(D(n,p))=2, where λ(n) tends to infinite.

Keywords: Directed proper connection number; Directed graphs; Random graphs (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300319304217
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:361:y:2019:i:c:p:169-174

DOI: 10.1016/j.amc.2019.05.028

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().