about the structure of components of tensor product if more than one bipartite graph is taken

Question

I was reading about tensor product of graphs. We know that if we take tensor product of n graphs and want this product to be a connected graph then at most one graph should be bipartite. In the book Handbook of Product graphs, its written that if we have k number of bipartite graphs then the number of components in this product will be $2^{k-1}$. I just want to know is there any way or known result by which we can get information about the structure and type of components of tensor product of graphs when more than one bipartite graph is taken into product. Any idea or hint will be of great help. Thanks.

Answer 1

Call the factor graphs $G_0$, $G_1$, etc. A vertex in the tensor product $P$ corresponds to a sequence $(g_0, g_1, g_2, \ldots)$, with $g_n\in G_n$. Since each $G_n$ is bipartite, its vertices can be divided into two sets $L_n$ and $R_n$, and all edges of $G_n$ are between vertices in $L_n$ and $R_n$. Thus, each $p\in P$ has a signature that is which sets each component $g_n$ is in. E.g., if $g_0\in L_0$, $g_1\in L_1$, $g_2\in R_2$, $g_3 \in L_3$, the signature is LLRL. Because the $G_n$ are bipartite, in $P$ two vertices are connected by an edge only if they have complementary signatures -- a vertex with signature LLRL can only be connected to a vertex with signature RRLR.

This shows that there are $2^{k-1}$ subsets of the tensor product that are not connected if there are $k$ factors, the subsets being the unions of the $2^k$ vertex sets with particular signatures with the vertex sets with their complementary signatures.

Assuming that each $G_n$ is connected (and has more than one vertex), you can show that any two vertexes with the same signature are connected by constructing a path: The first part of the path is the path by which the first component of the first vertex is connected to the first component of the second vertex, while the other components "rock back and forth" between their value in the first vertex and some vertex in the other set of their factor graph. The second part of the path is generated from a path between the second components of the two vertexes in a similar way. Etc.

If one of the factor graphs has $m$ connected components (each of which has at least two vertices), the tensor product falls into $m$ non-connected subsets. So the number of connected components of $k$ bipartite graphs, which respectively have $m_1,\ldots ,m_k$ connected components (bipartite graphs containing at least two vertices), is $m_1m_2\cdots m_k2^{k-1}$.

Answer 2

The adjacency matrix of a bipartite graph $G$ can be partitioned into $2\times 2$ blocks with the diagonal blocks zero. Let $B(G)$ be the upper right block. Let $H$ be another bipartite graph; define $B(H)$ similarly. Then the tensor product $G\otimes H$ consists of two bipartite components $X$ and $Y$, where $B(X)=B(G)\otimes B(H)$ and $B(Y)=B(G)\otimes B(H)^T$ (using the matrix tensor product). You can figure out what the edges of $X$ and $Y$ are from the definition of the matrix tensor product.

ADDED: An interest fact about the two components is that they have the same eigenvalues, except that if they are not of the same size the larger one has extra zero eigenvalues. This appeared in a paper I wrote with Chris Godsil in 1975.

Answer 3

Here's an alternative approach, which might allow using machinery from linear algebra. It's based on the sort of analysis used on Markov chains, and various details may well be wrong. The key idea is that the spectrum (multiset of eigenvalues) of the tensor product of two matrices is the multiset of pairwise products of each eigenvalue of the first matrix with each eigenvalue of the second matrix. This generalizes in the obvious way for a tensor product of $n$ matrices. Spectra are interesting, because the multiplicity of an eigenvalue $\lambda$ in the spectrum is (more or less) the dimension of the subspace of vectors which are sent to $\lambda$ times themselves when multiplied by the matrix.

Consider the adjacency matrix $G$ of the graph, but modify each row by dividing it by the total number of non-zero entries in the row. Rows that have no non-zero entries correspond to isolated vertices, and their entries remain zero. If we consider a vector $v$ as representing a probability distribution over the vertices, then $Gv$ is the probability distribution if the initial distribution "diffuses" one step -- the density at any one vertex diffuses in equal parts to all adjacent vertices (and none stays behind), where density at an isolated vertex goes away.

After playing with simple cases (the trivial graph, the minimal bipartite graph, cycles), I believe: (1) Each trivial component generates one eigenvalue $0$. (2) Each non-bipartite connected component with $k$ vertices generates one eigenvalue $1$ (representing the steady-state distribution on that component) and $k-1$ eigenvalues with absolute value between $0$ and $1$ that represent deviations from the steady-state distribution that "die out over time" in the diffusion model. (3) Each bipartite connected component with $k$ vertices generates one eigenvalue $1$ (representing the steady-state distribution), one eigenvalue $-1$ (representing the deviation from the steady-state distribution that oscillates stably between being one part and the other part of the bipartite component), and $k-2$ eigenvalues with absolute value between $0$ and $1$, representing decaying modes.

Now, looking at the spectrum of the tensor product $P$ of all the $G_i$ as the products of all combinations of eigenvalues of the $G_i$, taking one from each factor, we see -- where the number of connected components in $P$ is the sum of the multiplicities of $0$ and $1$:

$0$ eigenvectors of $P$ result when any factor eigenvalue is $0$. This corresponds to the enumerative result about the overpowering effects of a trivial connected component of a factor.

$1$ eigenvectors of $P$ result when all factor eigenvalues are $1$ or $-1$, and the number of $-1$ factors is even. This corresponds to the "signature" pairing in the enumerative result.

$-1$ eigenvectors of $P$ result from the same, except that the number of $-1$ factors is odd. Ditto correspondence.

All other combinations generate eigenvectors between $0$ and $1$, which do not represent connected components.

Answer 4

To generalize: Let $G_0 \ldots$ be general graphs. Separate each graph into its connected components. Since tensor product distributes over disjoint union, it suffices to consider the case where every $G_i$ is connected.

Connected graphs fall into three cases: (1) the trivial graph (one vertex, no edges), (2) non-trivial connected bipartite graphs, and (3) non-trivial connected non-bipartite graphs. Non-trivial connected non-bipartite graphs must contain a cycle of odd length.

If one factor in the product is the trivial graph, the tensor product is the totally disconnected graph with the obvious number of vertices (because it can contain no edges). So it suffices to consider the case where every $G_i$ is connected and non-trivial.

By the analysis above, the product can be separated into $2^{k-1}$ disconnected components (where there are $k$ factors that are bipartite) based on the signatures of the vertices of the product graph $P$. Each of those components is connected: E.g., if $G_0$ is non-bipartite, and $a$ and $b \in G_0$, and $g_i \in G_i$ for $i > 0$, and $G_i$ is non-trivial and connected, then $(a, g_1, \ldots)$ is connected to $(b, g_1, \ldots)$. It suffices to construct an even-length path from $a$ to $b$, because each $g_i$ is connected to some $g^\prime_i$, and so a suitable path in $P$ can be constructed from these elements. Because $G_0$ is connected, there is a path from $a$ to $b$. If the path is not already even-length, it can be made so by appending (1) a path from $b$ to some vertex $v$ in the odd-length cycle in $G_0$, (2) the path around the cycle from $v$ to $v$, and (3) the path back from $v$ to $b$.

We can add that the product graph of a set of connected non-trivial graphs is non-bipartite iff each factor is non-bipartite. This follows from (1) a connected non-trivial graph is non-bipartite iff it contains an odd-length cycle, (2) an odd-length cycle in the tensor product can be mapped into an odd-length cycle in each factor, and (3) if there is an odd-length cycle in each factor, they can be combined to form an odd-length cycle in the product graph (whose length is the product of the lengths of the factor cycles).