On subgraphs of Cartesian product graphs (Q1349090)

All graphs considered are finite undirected and simple ones. Such graphs which can be represented as nontrivial subgraphs of Cartesian product graphs are characterized. In general a graph \(G\) is prime with respect to a graph product \(*\) if it cannot be represented as a product of two nontrivial graphs, and \(G\) is called \(S\)-prime with respect to \(*\) if it cannot be represented as a nontrivial subgraph of a \(*\)-product graph. Graphs which are not \(S\)-prime are called \(S\)-composite. Here, among the graph products, the Cartesian product is invesigated. It is known that the Cartesian product \(G\square H\) of \(G= (V(G), E(G))\) and \(H= (V(H),E(H))\) is the graph with the vertex set \(V(G)\times V(H)\) where vertex \((a,x)\) is adjacent to vertex \((b,y)\) whenever \(ab\in E(G)\) and \(x= y\), or \(a=b\) and \((x,y)\in E(H)\). For a fixed \(a\) of \(G\), the vertices in \(\{(a,x)\mid x\in V(H)\}\) induce a subgraph of \(G\square H\) isomorphic to \(H\). At first \(S\)-prime graphs are represented. It is proved that a connected graph \(G\) on at least three vertices is \(S\)-composite iff there exists a path \(k\)-coloring of \(G\) with \(2\leq k\leq|V(G)|-1\) (Theorem 1); here a \(k\)-coloring of \(G\) is a surjective mapping \(c:V(G)\to \{1,2,\dots, k\}\). Two corollaries are deduced. Let Corollary 3 be mentioned: Let \(G\) be a bipartite graph with radius 2 and suppose that \(G\) contains no subgraph isomorphic to \(K_{2,3}\). Then \(G\) is \(S\)-composite. In a further chapter an infinite family of graphs is constructed which cannot be represented as nontrivial subgraphs of Cartesian product graphs and contain no proper representable subgraph. Therefore, so-called basic \(S\)-prime graphs recursively defined by Lamprey and Barnes as \(S\)-prime graphs on at least three vertices which contain no proper basic \(S\)-prime subgraphs are introduced. The authors show that this definition can be simplified. They prove that a given graph \(A_n\) for any \(n\geq 3\) (see Figure 1) is a basic \(S\)-prime graph (Theorem 6). It follows that \(A_3= K_{2,3}\), but only few basic \(S\)-prime graphs are known.