scientific article; zbMATH DE number 4031733
[For the entire collection see Zbl 0608.00004.] The mean distance \(\mu\) (G) of a connected graph G is the average over all pairs \(\{\) u,v\(\}\) of distinct vertices of G of the distance between u and v. The author presents some results and conjectures concerning the effect of a vertex removal, an edge removal and a vertex set partition on the mean distance. In particular he conjectures that every connected (respectively two-edge connected) graph has a vertex (respectively an edge), whose removal increases the mean distance by less than a factor of 4/3. These two conjectures, known as four-third conjectures, have been partially proved by several people including the author, D. Bienstock; E. Györi and M. Kouider.
- Average distances in undirected graphs and the removal of vertices
- Computing the average distance of an interval graph
- An upper bound on Wiener indices of maximal planar graphs
- Mean distance in a tree
- Disproof of a conjecture about average Steiner distance.
- Average distance in graphs with removed elements
- Edge-vulnerability and mean distance
- scientific article; zbMATH DE number 4123768 (Why is no real title available?)
- scientific article; zbMATH DE number 221409 (Why is no real title available?)
- Solution to a conjecture on the mean subtree order of graphs under edge addition
- On mean distance and girth
- An ``average distance inequality for large subsets of the cube
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 Q3772252)