2
$\begingroup$

A graph has 100 vertices. Each vertex is connected to exactly 10 other vertices such that the whole graph is connected. If I choose two random vertices of the graph, what is the length of the shortest path between them?

Basically in a school, there's 1000 students; each has 10 friends. If I randomly choose two students, how 'close' to each other are they?

$\endgroup$
  • $\begingroup$ do you mean 'the mean of the shortest path' because the 'shortest path' is obviously 1 edge $\endgroup$ – Alex Oct 1 '15 at 12:40
  • $\begingroup$ Yes, sorry, I mean what is the expected value of the length of the shortest path. Sorry for any confusion! $\endgroup$ – John Smith Oct 1 '15 at 12:44
  • $\begingroup$ The edge between 2 vertices, is it generated with some probability $p$? $\endgroup$ – Alex Oct 1 '15 at 12:46
  • 5
    $\begingroup$ You've to specify how the graph is chosen. Is it one of the connected 10-regular graphs each with equal probability? In any case such problems rarely have a nice exact answer. $\endgroup$ – user21820 Oct 1 '15 at 12:51
  • 1
    $\begingroup$ 1000 vertices or 100? $\endgroup$ – Morgan Rodgers Oct 1 '15 at 16:37
3
$\begingroup$

Let's suppose that these students go to Hypercube10 Highschool. In Mathematica, school = Graph[GraphData[{"Hypercube", 10}]] -- it's a graph with 1024 vertices and each vertex connects to 10 others.

hypercube10

We can get distances between 100000 random pairs of students.

data = Sort[Tally[Table[GraphDistance[school, RandomInteger[{1, 1024}], 
 RandomInteger[{1, 1024}]], {100000}]]]

{{0, 88}, {1, 968}, {2, 4392}, {3, 11658}, {4, 20845}, {5, 24618}, 
{6,20393}, {7, 11652}, {8, 4374}, {9, 923}, {10, 89}}

We'll want to throw out the 0's at the start. Totaling what's left

Total[Times @@ # & /@ Drop[data, 1]]/(100000 - data[[1, 2]]) // N 

We get 4.99747 ... quite close to 5. I'm going to guess 5 is a reasonably good answer. One way to consider this is the maximal spread from 1 student. There could be up to $10 \times 9 \times 9$ students at distance 4, but up to $10 \times 9 \times 9 \times 9 = 7290$ students at distance 5. But more than half the students are at distance 5.

If they went to Superclique Highschool instead, things would be different. There, students are friends in 100 ( $K_{10}$ - edge) cliques, with the cliques making $C_{100}$. There, the average distance seems to be 50.

We're assuming all students are connected. With 100 ( $K_{10}$ ) cliques, they wouldn't be.

There is a 13140 vertex degree-diameter graph with valence 10 and maximum distance 5 between students. There, the average distance is about 4.25.

So, it depends on how cliquish the high school is.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.