×

Distance regularity in direct-product graphs. (English) Zbl 0940.05071

Let \(G=(V,E)\) and \(H=(W,F)\) be graphs. The direct product \(G\times H\) of \(G\) and \(H\) is defined as follows: \(V(G\times H)=V\times W\) and \(E(G\times H)=\{\{(u,x),(v,y)\}:\{u,v\}\in E, \{x,y\}\in F\}\). In this paper the following results are obtained. If \(G\) and \(H\) are distance regular graphs of diameter at least two, then \(G\times H\) or a component of \(G\times H\) is distance regular iff each of \(G\) and \(H\) is isomorphic to \(K_{n,n}\) for some \(n\). If \(G\) is a distance regular graph of diameter at least two and \(n\geq 3\), then \(G\times K_n\) is not distance regular.

MSC:

05E30 Association schemes, strongly regular graphs
05C12 Distance in graphs
Full Text: DOI

References:

[1] Weichsel, P. M., Distance-regular subgraphs of a cube, Discrete Math, 109, 297-306 (1992) · Zbl 0782.05029
[2] Brouwer, A. E.; Cohen, A. M.; Neumaier, A., Distance-Regular Graphs (1989), Springer-Verlag · Zbl 0747.05073
[3] Weichsel, P. M., Products of highly regular graphs, (Bondy, J. A.; Murty, U. S.R., Progress in Graph Theory (1984), Academic Press) · Zbl 0218.05061
[4] Jha, P. K.; Klavžar, S.; Zmazek, B., Isomorphic components of Kronecker product of bipartite graphs, Discuss Math-Graph Theory, 17, 301-309 (1997) · Zbl 0906.05050
[5] Kim, S.-R., Centers of a tensor-composite graph, (Congr. Numer., 81 (1991)), 193-204 · Zbl 0765.05093
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.