A remark on cancellation in direct products of graphs. (English) Zbl 0663.05053

Zelinka, Bohdan

Čas. Pěstování Mat. 114, No. 1, 35-38 (1989).

The direct product of two graphs G, G’ is the graph \(G\times G'\) whose vertex set is the Cartesian product of vertex sets of G and G’ and in which two vertices \((\nu_ 1,\nu '_ 1)\), \((\nu_ 2,\nu '_ 2)\) are adjacent if and only if \(\nu_ 1\), \(\nu_ 2\) are adjacent in G and \(\nu '_ 1\), \(\nu '_ 2\) are adjacent in G’. There exists a family \({\mathfrak F}\) of the power of continuum consisting of pairwise non-isomorphic locally connected non-bipartite graphs with the property that for every bipartite graph G and for any two graphs \(G_ 1\), \(G_ 2\) from \({\mathfrak F}\) the graphs \(G\times G_ 1\), \(G\times G_ 2\) are isomorphic. For every positive integer n there exists such a family of finite graphs which has the cardinality greater than n. This is a negative solution of a problem by V. Puš.

MSC:

05C99

Graph theory

Keywords:

direct product of graphs; isomorphism of graphs; bipartite graph