Strong product of graphs

In graph theory, the strong product is a way of combining two graphs to make a larger graph. Two vertices are adjacent in the strong product when they come from pairs of vertices in the factor graphs that are either adjacent or identical. The strong product is one of several different graph product operations that have been studied in graph theory. The strong product of any two graphs can be constructed as the union of two other products of the same two graphs, the Cartesian product of graphs and the tensor product of graphs.

An example of a strong product is the king's graph, the graph of moves of a chess king on a chessboard, which can be constructed as a strong product of path graphs. Decompositions of planar graphs and related graph classes into strong products have been used as a central tool to prove many other results about these graphs.

Care should be exercised when encountering the term strong product in the literature, since it has also been used to denote the tensor product of graphs.^[1]

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]