graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, 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 In graph theory, the Cartesian product of graphs and is a graph such that: * the vertex set of is the Cartesian product ; and * two vertices and are adjacent in if and only if either ** and is adjacent to in , or ** and is adjace ...

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.

Definition and example

The strong product of

graphs Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties * Graph (topology), a topological space resembling a graph in the sense of discre ...

and is a graph such that the vertex set of is the Cartesian product ; and distinct vertices and are adjacent in

if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...

: : and is adjacent to , or : and is adjacent to , or : is adjacent to and is adjacent to . It is the union of the

Cartesian product In mathematics, specifically set theory, the Cartesian product of two sets and , denoted , is the set of all ordered pairs where is an element of and is an element of . In terms of set-builder notation, that is A\times B = \. A table c ...

and the

tensor product In mathematics, the tensor product V \otimes W of two vector spaces V and W (over the same field) is a vector space to which is associated a bilinear map V\times W \rightarrow V\otimes W that maps a pair (v,w),\ v\in V, w\in W to an element of ...

. For example, the king's graph, a graph whose vertices are squares of a

chessboard A chessboard is a game board used to play chess. It consists of 64 squares, 8 rows by 8 columns, on which the chess pieces are placed. It is square in shape and uses two colours of squares, one light and one dark, in a chequered pattern. During p ...

and whose edges represent possible moves of a chess king, is a strong product of two

path graph In the mathematical field of graph theory, a path graph (or linear graph) is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two termina ...

s. 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.

Properties and applications

Every

planar graph In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...

is a subgraph of a strong product of a path and a graph of

treewidth In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests ...

at most six. This result has been used to prove that planar graphs have bounded queue number, small universal graphs and concise adjacency labeling schemes, and bounded nonrepetitive chromatic number and centered chromatic number. This product structure can be found in

linear time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations ...

. Beyond planar graphs, extensions of these results have been proven for graphs of bounded

genus Genus (; : genera ) is a taxonomic rank above species and below family (taxonomy), family as used in the biological classification of extant taxon, living and fossil organisms as well as Virus classification#ICTV classification, viruses. In bino ...

, graphs with a forbidden minor that is an apex graph, bounded-degree graphs with any forbidden minor, and k-planar graphs. The

clique number In graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph G is an induced subgraph of G that is complete. Cliques are one of t ...

of the strong product of any two graphs equals the product of the clique numbers of the two graphs. 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. 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

k

. If

G

is a

k

-leaf power of a tree

T

, then

T

can be found as a subgraph of a strong product of

G

with a

k

-vertex cycle. This embedding has been used in recognition algorithms for leaf powers. The strong product of a 7-vertex

cycle graph In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...

and a 4-vertex

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices i ...

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

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.

References

{{Reflist Graph products