×

On the number of reachable pairs in a digraph. (English) Zbl 1444.05061

Summary: A pair \((u,v)\) of (not necessarily distinct) vertices in a directed graph \(D\) is called a reachable pair if there exists a directed path from \(u\) to \(v\). We define the weight of \(D\) to be the number of reachable pairs of \(D\), which equals the sum of the number of vertices in \(D\) and the number of directed edges in the transitive closure of \(D\). In this paper, we study the set \(W(n)\) of possible weights of directed graphs on \(n\) labeled vertices. We prove that \(W(n)\) can be determined recursively and describe the integers in the set. Moreover, if \(b(n)\geqslant n\) is the least integer for which there is no digraph on \(n\) vertices with exactly \(b(n)+1\) reachable pairs, we determine \(b(n)\) exactly through a simple recursive formula and find an explicit function \(g(n)\) such that \(|b(n)-g(n)|<2n\) for all \(n\geqslant 3\). Using these results, we are able to approximate \(|W(n)|\) – which is quadratic in \(n\) – with an explicit function that is within \(30n\) of \(|W(n)|\) for all \(n\geqslant 3\), thus answering a question of A. R. Rao [Discrete Math. 306, No. 14, 1595–1600 (2006; Zbl 1098.05037)]. Since the weight of a directed graph on \(n\) vertices corresponds to the number of elements in a preorder on an \(n\) element set and the number of containments among the minimal open sets of a topology on an \(n\) point space, our theorems are applicable to preorders and topologies.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C30 Enumeration in graph theory

Keywords:

reachable pair

Citations:

Zbl 1098.05037

Software:

Stony Brook
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] P. Alexandroff, Diskrete R¨aume,Rec. Math. [Mat. Sbornik] (N.S.)2 (1937), 501- 519. · JFM 63.1163.01
[2] J. Bang-Jensen and G. Gutin,Digraphs. Theory, algorithms, and applications (Second edition). Springer Monographs in Mathematics. Springer-Verlag London, Ltd., 2009. · Zbl 1170.05002
[3] J. A. Bondy and U. S. R. Murty,Graph Theory with Applications, American Elsevier Publishing Co., Inc., New York (1976). · Zbl 1226.05083
[4] M. Ern´e, On the cardinalities of finite topologies and the number of antichains in partially ordered sets,Discrete Math.35 (1981), 119-133. · Zbl 0465.05009
[5] R. Parchmann, On the cardinalities of finite topologies,Discrete Math.11 (1975), 161-172. · Zbl 0295.54002
[6] A. R. Rao, The number of reachable pairs in a digraph,Discrete Math.306 (2006), no. 14, 1595-1600. · Zbl 1098.05037
[7] K. Ragnarsson and B. E. Tenner, Obtainable sizes of topologies of finite sets,J. Combin. Theory Ser. A117 (2010), 138-151. · Zbl 1189.05038
[8] H. Sharp, Jr., Quasi-orderings and topologies on finite sets,Proc. Amer. Math. Soc.17 (1966), 1344-1349. · Zbl 0151.29503
[9] S. S. Skiena,The Algorithm Design Manual(Second edition), Springer (2011). · Zbl 0885.68002
[10] R. P. Stanley, On the number of open sets of finite topologies,J. Combin. Theory 10 (1971), 74-79. · Zbl 0214.21001
[11] Wolfram Research, Inc.
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.