The number of reachable pairs in a digraph |
| |
Authors: | AR Rao |
| |
Institution: | Stat-Math Unit, Indian Statistical Institute, 203 B. T. Road, Kolkata 700 108, India |
| |
Abstract: | For a digraph G, let R(G) (respectively, R(k)(G)) be the number of ordered pairs (u,v) of vertices of G such that u≠v and v is reachable from u (respectively, reachable from u by a path of length ?k). In this paper, we study the range Sn of R(G) and the range of R(k)(G) as G varies over all possible digraphs on n vertices. We give a sufficient condition and a necessary condition for an integer to belong to Sn. These determine the set Sn for all n?208. We also determine for k?4 and show that whenever n?k+(k+1)0.57+2, for arbitrary k. |
| |
Keywords: | Digraph Reachable pairs Reachability index |
本文献已被 ScienceDirect 等数据库收录! |
|