[A problem posed by Robert Johnson]
At the seminar talk by Graham Bent, Patrick Dantressangle (both IBM) and Mark Walters (QM) last term the problem of forcing a graph to evolve in such a way that it keeps the property of being well-connected (in some sense) was discussed. Tangentially they mentioned the problem of how to join up two disjoint graphs without using any information about their structure in such a way that the resulting graph is well-connected. One physical example they gave was that the two graphs represent lines of communication between tanks belonging to two armies who wish to form an alliance. This document is an attempt to distill some mathematical questions out of this vague problem. If anyone is interested in thinking about these question more seriously then let me know and we could meet up to knock some ideas around. I have a longer document with a few more observations which I am happy to share.
The general (very vague) question is: Given two connected graphs and on disjoint vertex sets and a number , how should we add edges between and to make the resulting graph highly connected without using knowledge of where vertices are in and ?
More specifically consider the following method for generating a graph which does not use any knowledge of the structure of and :
- Choose positive integers so that ,
- Pick vertices at random in and join each to randomly chosen vertices in ,
- Pick vertices at random in and join each to randomly chosen vertices in .
Assume for now that all random choices are made uniformly. We will refer to this process as connecting and blindly. How should the be chosen to make the resulting graph as highly connected as it can be in some appropriate sense?
We will use the average distance between a vertex in and a vertex in to measure well-connectedness:
From the point of view of the original motivation the most interesting case may be where and have been generated by some kind of random preferential attachment procedure but as a warm-up one could think about the case when they are both long cycles. Even this special case seems to generate some non-trivial questions and it will be the only case we consider in any detail here.
Question: Let and be two copies of on disjoint vertex sets. Given , how should be chosen so that when the graphs are joined blindly, is as small as it can be?
A speculative guess would be that out of all ways to connect two copies of blindly the best is to either take independent edges (that is, setting , , ) or to take two equally sized stars one in each copy of (that is, setting , ). Moreover one would expect the first of these to be better for small and the second to be better for large .
There are several possible variants of this problem. It would for instance be possible to make all our random choices of vertices not uniformly at random but choosing vertices of higher degree with higher probability (as in a preferential attachment model). However this uses some information on the structure of the graphs so is perhaps not truly blind. The question of how to choose and the still arises in the preferential attachment version so it seems worthwhile to consider this issue first in the simpler uniform version.
Another variant would be to change the measure of well-connectedness to something other than . There are several natural possibilities including the average distance between any two vertices in , the diameter of , or the average effective resistance when is viewed as a resistor network.
A more general way of connecting and would be to take a bipartite graph with edges and insert a copy of it between and choosing at random where to embed the vertices in each. Our original blind connection process corresponds to the situation where is a disjoint union of stars. Allowing to be an arbitrary bipartite graph would require some coordination between the vertices so again is perhaps not truly blind. However this may still be reasonable for some applications and might also be an easier situation to analyse. A natural guess at the best would be a double star (a centre in and a centre in joined to each other and each with leaves in the other graph assuming is odd).
Question: Let and be two copies of on disjoint vertex sets. In this new model, can be smaller than that achieved by a double star?