×

Distance regularity of compositions of graphs. (English) Zbl 1063.05137

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.

MSC:

05E30 Association schemes, strongly regular graphs
05C12 Distance in graphs
05C75 Structural characterization of families of graphs
Full Text: DOI

References:

[1] Bannai, E.; Ito, T., (Algebraic Combinatorics, I: Association Schemes, Benjamin- Cummings Lecture Notes, Ser. 58 (1993)), London
[2] Biggs, N., Algebraic Graph Theory (1993), Cambridge University Press: Cambridge University Press Cambridge, U.K
[3] Brouwer, A. E.; Cohen, A. M.; Neumaier, A., Distance-Regular Graphs (1989), Springer-Verlag: Springer-Verlag Berlin · Zbl 0747.05073
[4] Berge, C., Graphs and Hypergraphs (1973), North-Holland: North-Holland Amsterdam · Zbl 0483.05029
[5] Cvetković, D., Graphs and their spectra, (Thesis, Univ. Beograd Publ. Elektrotehn. Fak., Ser. Mat. Fiz., No. 354-356 (1971)), 1-50 · Zbl 0238.05102
[6] Cvetković, D.; Doob, M.; Sachs, H., Spectra of Graphs—Theory and Application (1995), Johann Ambrosius Barth Verlag: Johann Ambrosius Barth Verlag Heidelberg-Leipzig · Zbl 0824.05046
[7] Song, S. Y., Products of distance-regular graphs, Util. Math., 29, 173-175 (1986) · Zbl 0576.05040
[8] Aggarwal, S.; Jha, P. K.; Vikram, M., Distance regularity in direct-product graphs, Appl. Math. Lett., 13, 1, 51-55 (2000) · Zbl 0940.05071
[9] Stevanović, D., When is NEPS of graphs connected?, Linear Algebra Appl., 301, 137-144 (1999) · Zbl 0942.05034
[10] Egawa, Y., Characterization of \(H(n,q)\) by the parameters, J. Combin. Theory, Ser. A, 81, 108-125 (1981) · Zbl 0472.05056
[11] Shrikhande, S. S., The uniqueness of the \(L_2\) association scheme, Ann. Math. Statist., 80, 781-798 (1959) · Zbl 0086.34802
[12] Brualdi, R. A.; Shen, J., Diameter of the NEPS of bipartite graphs, Discrete Math., 226, 1-3, 373-376 (2001) · Zbl 0966.05025
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.