scientific article; zbMATH DE number 4031733

From MaRDI portal
Publication:3772252





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











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)