4
$\begingroup$

Context: This problem came up in the design of circuitboards.

Consider a bipartite graph $G$, colored $\color{red}{\text{red}}$ and $\color{blue}{\text{blue}}$. It's a biregular graph, which means that the valency (=degree) of each blue vertex is the same as every other blue vertex, and likewise for the reds.

In my particular example, there are $\color{red}{32}$ red vertices and $\color{blue}{24}$ blue vertices. The valency of the reds are $6$, and the valency of the blues as $8$. Note that $32 \times 6 = 24 \times 8$.

enter image description here

The question is:

Is there a biregular graph with the above parameters that satisfies the minimum (geodesic) distance between every pair of distinct red vertices is $2$?

If not, how many blue vertices need to be added to guarantee the existence of such a solution?

I'll worry about actually finding the solution once I determine whether or not it exists.

My progress:

The adjacency matrix $\mathbf A$, considered as a block matrix, is of the form:

$$\mathbf A = \begin{bmatrix} \color{red}{\mathbf{0}_{32^2}} & \color{purple}{ \mathbf M_{32 \times 24}} \\ \color{purple}{ \mathbf M^\intercal_{24 \times 32}} & \color{blue}{\mathbf{0}_{24^2}} \end{bmatrix}$$

The degree constraint means that $\color{purple}{\mathbf M}$ will have each row sum equal to $6$, and each column sum equal to $8$.

The matrix $\mathbf A^2$ the number of walks of length $2$ between any two vertices:

$$\mathbf A^2 =\begin{bmatrix} \color{red}{\mathbf{MM^\intercal}_{32^2}} & \color{purple}{\mathbf 0_{32\times24}} \\ \color{purple}{\mathbf 0_{24\times32}} & \color{blue}{\mathbf{M^\intercal M}_{24^2}} \end{bmatrix}$$

Because I'm interested only in the red-to-red paths, only $\mathbf {\color{red}{MM^\intercal}}$ is of interest. If a solution exists, there exists an $\mathbf{\color{red}{MM^\intercal}}$ with every off-diagonal entry $>0$.

$\endgroup$
3
+150
$\begingroup$

We can do this.

In fact, we can do this with only $\color{blue}{20}$ blue vertices (red degrees being reduced to $5$). So we have $4$ extra blue vertices whose adjacencies can be determined arbitrarily at the end (as long as they all have different neighbors, and therefore increase the degree of every red vertex by exactly $1$).

In fact, we can do something harder still: find such a bipartite graph with $\color{red}{16}$ red vertices and $\color{blue}{20}$ blue vertices in which every red vertex has degree $5$, every blue vertex has degree $4$, and any two red vertices have exactly one blue vertex in common.

This is just a $(16,4,1)$ block design. (Look up block designs for solutions to such problems more generally!) Here is one possible solution. (Each red vertex is a letter between A and P; each block of $4$ letters below represents the adjacency list of a blue vertex. In this solution, every row of blue vertices covers each red vertex once. One way to get such a solution is to look at the points and lines in an affine plane over $\mathbb F_4$.)

ABCD    EFGH    IJKL    MNOP
AEIM    BFJN    CGKO    DHLP
AFKP    BELO    CHIN    DGJM
AGLN    BHKM    CEJP    DFIO
AHJO    BGIP    CFLM    DEKN

To go from this to the original problem with $\color{red}{32}$ red vertices, just replace each red vertex by two copies with the same adjacent blue vertices. This doubles the blue degree (from $4$ to $8$). The $16$-vertex solution becomes:

AaBbCcDd    EeFfGgHh    IiJjKkLl    MmNnOoPp
AaEeIiMm    BbFfJjNn    CcGgKkOo    DdHhLlPp
AaFfKkPp    BbEeLlOo    CcHhIiNn    DdGgJjMm
AaGgLlNn    BbHhKkMm    CcEeJjPp    DdFfIiOo
AaHhJjOo    BbGgIiPp    CcFfLlMm    DdEeKkNn

Here is this solution in unhelpful picture format, just for fun.

solution

To go from this to a solution with $\color{blue}{24}$ blue vertices, we could just double the first row (that is, add $4$ more blue vertices with the same adjacencies as the blue vertices in the first row of the solution above). This has the effect of increasing every red degree by exactly $1$. Of course, there are many other ways to do this.

$\endgroup$
  • $\begingroup$ Neat! Is there a way to extend this method to create a symmetric graph? Symmetric being, for example, that the upper-left $16 \times 12$ block submatrix of $M$ is eqaul to the lower-right $16\times 12$ block submatrix of $M$ $\endgroup$ – GFauxPas Nov 8 '17 at 19:16
  • 1
    $\begingroup$ The original $16 \times 20$ graph is very symmetric; since it's an affine-plane construction, given any two triples $(r_1, r_2, r_3)$ and $(r_1', r_2', r_3')$ of red vertices, if neither triple is on the adjacency list of a blue vertex, then there's a graph automorphism sending one triple to the other. The $32 \times 24$ graph should still have some symmetries that preserve the blocks $\{A,B,C,D\}$, $\{a,b,c,d\}$, $\{E,F,G,H\}$, and so on. $\endgroup$ – Misha Lavrov Nov 8 '17 at 21:20
0
$\begingroup$

There isn't a biregular graph with the above parameters that satisfies the minimum (geodesic) distance between every pair of distinct red vertices is 2. Proof. Suppose such biregular graph exists. Then at least 4 blue "transit" vertices must exist for every red vertice to be connected with other by the path of length 2. So, the number of blue vertices must be at least $(32\times 4)/2=64$.

Consequently, the answer to the second question is probably 40. If we fix the valency of the blues as 8, then valency of the reds must be 16.

$\endgroup$
  • $\begingroup$ I believe you're over-counting. $\endgroup$ – Misha Lavrov Oct 24 '17 at 0:38

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.