The average geodesic distance L Newman (2003) and the compactness C.sub.B Botafogo (1992) are important graph indices in applications of complex network theory to real-world problems. Here, for simple connected undirected graphs G of order n, we study the behavior of L(G) and C.sub.B (G), subject to the condition that their order |V(G)| approaches infinity. We prove that the limit of L(G)/n and C.sub.B (G) lies within the interval 0;1/3 and 2/3;1, respectively. Moreover, for any not necessarily rational number beta element of 0;1/3 (alpha element of 2/3;1) we show how to construct the sequence of graphs {G}, |V(G)| = n right arrow infinity, for which the limit of L(G)/n (C.sub.B (G)) is exactly beta (alpha) (Theorems 1 and 2). Based on these results, our work points to novel classification possibilities of graphs at the node level as well as to the information-theoretic classification of the structural complexity of graph indices.