The number and average length of subpaths in graphs

Abstract

We study extremal questions on the average length and the number of subpaths in a graph. In particular, we prove the questions of Jamison (from $1983,1984$) for the analogous concept of the average length of a subpath. Among other results, we prove that $K_n$ maximizes the average path length.

arXiv comment7 pages, 3 figures Manuscript was intended to gain insight in some of Jamison's problems, by studying those in the alternative setting of average (sub)path length. It will not be submitted to a journal