Distance regularity of compositions of graphs. (Q1764515)

The strong sum of graphs \(G_1\) and \(G_2\), \( G_1 \oplus G_2 \), is the graph whose vertex set is the Cartesian product \(V(G_1) \times V(G_2)\), and \((u_1,v_1)\) is adjacent to \((u_2,v_2)\) if \(u_1\) is adjacent to \(u_2\) and \(v_1\) is adjacent to \(v_2\) or if \(u_1\) is adjacent to \(u_2\) and \(v_1 = v_2\). The strong product \(G_1 \otimes G_2\) has the same vertex set and \((u_1,v_1)\) is adjacent to \((u_2,v_2)\) if \(u_1\) is adjacent to \(u_2\) and \(v_1\) is adjacent to \(v_2\) or if \(u_1\) is adjacent to \(u_2\) and \(v_1 = v_2\) or if \(u_1 = u_2\) and \(v_1\) is adjacent to \(v_2\). The main question of the paper is the one of determining the circumstances under which the strong sum or the strong product of distance regular graphs is distance regular. The author obtains a complete classification of the above situation(s). For the case of the strong product, the main theorem asserts that the strong product \(G_1 \otimes G_2\) of two connected distance regular graphs is distance regular if and only if both \(G_1\) and \(G_2\) are complete (of possibly different sizes). The case of the strong sum splits into two cases depending on the size of the first graph: if \(G_1\) has at least three vertices, and both \(G_1\) and \(G_2\) are connected and distance regular, then \(G_1 \oplus G_2\) is distance regular if and only if \(G_1\) is isomorphic to the complete multipartite graph with \(t\) parts of size \(m\) (for some \(t\) and \(m\)) and \(G_2\) is a complete graph; in the case when \(G_1=K_2\) and \(G_2\) is connected and distance regular, \(G_1 \oplus G_2\) is distance regular if and only if \(G_2\) satisfies two additional conditions on its distance parameters (stated in the form of equations). The key to the classification is a careful examination of the distance properties of the strong sum and strong product of connected graphs.