Diameter of the NEPS of bipartite graphs (Q1841924)

The authors study the graph \(G=\text{NEPS}(G_1, G_2,\dots, G_n;{\mathcal B})\) (non-complete, extended \(p\)-sum), where (1) \(G_1,G_2,\dots, G_n\) are simple graphs with nonempty vertex sets; (2) \({\mathcal B}\) is a nonempty set of nonzero binary \(n\)-tuples with some property; (3) the vertex set of \(G\) is \(V(G_1)\times V(G_2)\times\cdots\times V(G_n)\); and (4) the edge set of \(G\) is defined in the paper. Assume that each of the graphs \(G_i\) is connected and bipartite. The authors prove that if the graph \(G=\text{NEPS}(G_1,\dots, G_n;{\mathcal B})\) is connected, then \(G\) has a diameter which does not exceed the sum of the diameters of \(G_i\). Moreover, they characterize the case of equality.