On subgraphs of Cartesian product graphs (Q1349090): Difference between revisions

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.