On the number of reachable pairs in a digraph

zbMATH Open1444.05061arXiv1709.05390MaRDI QIDQ3300699FDOQ3300699

Authors: Eric Swartz, Nicholas J. Werner 

Publication date: 29 July 2020

Abstract: 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)geqslantn$ 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 $ngeqslant3$. 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 $ngeqslant3$, thus answering a question of Rao. 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.

Full work available at URL: https://arxiv.org/abs/1709.05390

Recommendations

• The number of reachable pairs in a digraph
• Reachability relations in digraphs
• Plurality preference digraphs realized by trees. II: On realization numbers
• Reachability relations and the structure of transitive digraphs
• scientific article; zbMATH DE number 969185

zbMATH Keywords

reachable pair

Mathematics Subject Classification ID

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

Cites Work

• Graph theory with applications
• Digraphs
• Title not available (Why is that?)
• On the cardinalities of finite topologies and the number of antichains in partially ordered sets
• On the number of open sets of finite topologies
• On the cardinalities of finite topologies
• Obtainable sizes of topologies on finite sets
• Quasi-Orderings and Topologies on Finite Sets
• The number of reachable pairs in a digraph

Cited In (3)

• Reachability relations in digraphs
• The number of reachable pairs in a digraph
• Title not available (Why is that?)

Uses Software

• Stony Brook

This page was built for publication: On the number of reachable pairs in a digraph

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