Re: average distance in a graph
- From: "Felix Goldberg" <felixg@xxxxxxxxxxxxxxxxxxxxxxx>
- Date: 15 Jun 2005 01:30:47 -0700
In the 1980's there was work done on somewhat similar questions,
starting from a conjecture by Peter Winkler that every graph has a
vertex (or edge) whose removal increases the mean distance by a factor
of at most 4/3. The pointer to this is (from Zentralblatt):
Zbl 0634.05042
Winkler, Peter
Mean distance and the `four-thirds conjecture'. (English)
[CA] Combinatorics, graph theory, and computing, Proc. 17th Southeast.
Conf., Boca Raton/Fl. 1986, Congr. Numerantium 54, 63-72 (1986).
I _think_ this conjecture was later proved but am not sure. Special
cases certainly were proved (see the review mentioned above).
HTH,
Felix.
Aldar C-F. Chan wrote:
> If a graph G has an average distance d, that is, the mean of
> the shortest path distance between any two vertices, if a vertices
> and b edges are deleted from G randomly, by how much the
> average distance would increase? Is there any upper/lower
> bound on this? Would it be sensitive to which edges are deleted
> if the edges are not randomly picked?
>
> Thanks.
.
- References:
- average distance in a graph
- From: Aldar C-F. Chan
- average distance in a graph
- Prev by Date: Re: morphism of principal fiber bundles
- Next by Date: ad* and Diff(R^2)
- Previous by thread: Re: average distance in a graph
- Next by thread: Re: average distance in a graph
- Index(es):
Relevant Pages
|
