Strong product of graphs

The strong product G ⊠ H of graphs G and H is a graph such that[2] the vertex set of G ⊠ H is the Cartesian product V(G) × V(H); and distinct vertices (u,u' ) and (v,v' ) are adjacent in G ⊠ H if and only if:

u = v and u' is adjacent to v', or

u' = v' and u is adjacent to v, or

u is adjacent to v and u' is adjacent to v'.

It is the union of the Cartesian product and the tensor product.

For example, the king's graph, a graph whose vertices are squares of a chessboard and whose edges represent possible moves of a chess king, is a strong product of two path graphs. Its horizontal edges come from the Cartesian product, and its diagonal edges come from the tensor product of the same two paths. Together, these two kinds of edges make up the entire strong product.[3]

Every planar graph is a subgraph of a strong product of a path and a graph of treewidth at most six.[4][5] This result has been used to prove that planar graphs have bounded queue number,[4] small universal graphs and concise adjacency labeling schemes,[6][7][8][9] and bounded nonrepetitive chromatic number[10] and centered chromatic number.[11] This product structure can be found in linear time.[12][13] Beyond planar graphs, extensions of these results have been proven for graphs of bounded genus,[4][14] graphs with a forbidden minor that is an apex graph,[4] bounded-degree graphs with any forbidden minor,[15] and k-planar graphs.[16]

The clique number of the strong product of any two graphs equals the product of the clique numbers of the two graphs.[17] If two graphs both have bounded twin-width, and in addition one of them has bounded degree, then their strong product also has bounded twin-width.[18]

A leaf power is a graph formed from the leaves of a tree by making two leaves adjacent when their distance in the tree is below some threshold ${\displaystyle k}$. If ${\displaystyle G}$ is a ${\displaystyle k}$-leaf power of a tree ${\displaystyle T}$, then ${\displaystyle T}$ can be found as a subgraph of a strong product of ${\displaystyle G}$ with a ${\displaystyle k}$-vertex cycle. This embedding has been used in recognition algorithms for leaf powers.[19]

The strong product of a 7-vertex cycle graph and a 4-vertex complete graph, ${\displaystyle C_{7}\boxtimes K_{4}}$, has been suggested as a possibility for a 10-chromatic biplanar graph that would improve the known bounds on the Earth–Moon problem; another suggested example is the graph obtained by removing any vertex from ${\displaystyle C_{5}\boxtimes K_{4}}$. In both cases, the number of vertices in these graphs is more than 9 times the size of their largest independent set, implying that their chromatic number is at least 10. However, it is not known whether these graphs are biplanar.[20]