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.7637879848480225
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