No label defined (Q3976631)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 19201
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 19201

      Statements

      26 June 1992
      0 references
      path length distribution
      0 references
      0 references
      [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\).
      0 references

      Identifiers