Connecting Graphs Blindly

[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 G_A and G_B on disjoint vertex sets and a number m, how should we add m edges between G_A and G_B to make the resulting graph G highly connected without using knowledge of where vertices are in G_A and G_B?

More specifically consider the following method for generating a graph which does not use any knowledge of the structure of G_A and G_B:

  • Choose positive integers a_1,\dots,a_k,b_1,\dots,b_l so that \sum a_i+\sum b_i=m,
  • Pick k vertices v_1,\dots,v_k at random in G_B and join each v_i to a_i randomly chosen vertices in G_A,
  • Pick l vertices u_1,\dots,u_l at random in G_A and join each u_i to b_i randomly chosen vertices in G_B.

Assume for now that all random choices are made uniformly. We will refer to this process as connecting G_A and G_B blindly. How should the a_i,b_i be chosen to make the resulting graph G as highly connected as it can be in some appropriate sense?

We will use the average distance between a vertex in G_A and a vertex in G_B to measure well-connectedness:
\displaystyle D=\frac{1}{|V(G_A)||V(G_B)|}\sum_{a\in V(G_A),b\in V(G_B)} d_G(a,b).

From the point of view of the original motivation the most interesting case may be where G_A and G_B 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 G_A and G_B be two copies of C_n on disjoint vertex sets. Given m, how should k,l,a_1,\dots,a_k,b_1,\dots,b_l be chosen so that when the graphs are joined blindly, \mathbb{E}(D) is as small as it can be?

A speculative guess would be that out of all ways to connect two copies of C_n blindly the best is to either take m independent edges (that is, setting k=m, l=0, a_1=a_2=\dots=a_k=1) or to take two equally sized stars one in each copy of C_n (that is, setting k=l=1, a_1=\lfloor\frac{m}{2}\rfloor,b_1=\lceil\frac{m}{2}\rceil). Moreover one would expect the first of these to be better for small m and the second to be better for large m.

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 k,l and the a_i,b_i 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 D. There are several natural possibilities including the average distance between any two vertices in G, the diameter of G, or the average effective resistance when G is viewed as a resistor network.

A more general way of connecting G_A and G_B would be to take a bipartite graph H with m edges and insert a copy of it between G_A and G_B choosing at random where to embed the vertices in each. Our original blind connection process corresponds to the situation where H is a disjoint union of stars. Allowing H 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 H would be a double star (a centre in G_A and a centre in G_B joined to each other and each with \frac{m-1}{2} leaves in the other graph assuming m is odd).

Question:  Let G_A and G_B be two copies of C_n on disjoint vertex sets. In this new model, can \mathbb{E}(D) be smaller than that achieved by a double star?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s