scientific article; zbMATH DE number 19201

From MaRDI portal
Publication:3976631





[For the entire collection see Zbl 0734.00014.] Let \(G\) be a graph of order \(n\). Then the path length distribution of \(G\) is \((x_ 1,\ldots,x_ n)\), where for \(i\geq 2\), \(x_ i\) is the number of pairs of distinct vertices of \(G\) connected by a path with \(i\) vertices and \(x_ 1\) is the number of pairs of distinct vertices of \(G\) connected by no path. Then, for example, \(x_ n=n(n-1)/2\) if and only if \(G\) is hamiltonian-connected. In 1976, Faudree and Schelp posed fourteen open question about the path length distribution of a graph. In this paper partial solutions to the 1st, 2nd, 3rd and 4th questions are given. Also, the conjecture associated with the 12th question is disproved. In particular, Faudree and Schelp conjectured that if \(x_ n=n(n-1)/2\) then \(x_ i=n(n-1)/2\) for \(n/2+1\leq i\leq n\). Here the author gives an example of a graph for which \(x_ n=n(n-1)/2\) but \(x_{n/2+1}\neq n(n-1)/2\).











This page was built for publication:

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