# 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?