Article ID Journal Published Year Pages File Type
4651453 Discrete Mathematics 2006 6 Pages PDF
Abstract

For a digraph G  , let R(G)R(G) (respectively, R(k)(G)R(k)(G)) be the number of ordered pairs (u,v)(u,v) of vertices of G   such that u≠vu≠v and vv is reachable from u (respectively, reachable from u   by a path of length ⩽k⩽k). In this paper, we study the range SnSn of R(G)R(G) and the range Sn(k) of R(k)(G)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 SnSn. These determine the set SnSn for all n⩽208n⩽208. We also determine Sn(k) for k⩽4k⩽4 and show that Sn(k)={0,1,…,n(n-1)} whenever n⩾k+(k+1)0.57+2n⩾k+(k+1)0.57+2, for arbitrary k.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,