graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, 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 In graph theory, a graph product is a binary operation on Graph (discrete mathematics), graphs. Specifically, it is an operation that takes two graphs and and produces a graph with the following properties: * The vertex (graph theory), vertex ...

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 Cartesian means of or relating to the French philosopher René Descartes—from his Latinized name ''Cartesius''. It may refer to: Mathematics *Cartesian closed category, a closed category in category theory *Cartesian coordinate system, modern ...

and the

tensor product of graphs In graph theory, the tensor product of graphs and is a graph such that * the vertex set of is the Cartesian product ; and * vertices and are adjacent in if and only if ** is adjacent to in , and ** is adjacent to in . The tensor prod ...

. An example of a strong product is the

king's graph In graph theory, a king's graph is a graph that represents all legal moves of the king chess piece on a chessboard where each vertex represents a square on a chessboard and each edge is a legal move. More specifically, an n \times m 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" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bicondi ...

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

union Union commonly refers to: * Trade union, an organization of workers * Union (set theory), in mathematics, a fundamental operation on sets Union may also refer to: Arts and entertainment Music * Union (band), an American rock group ** ''Un ...

of the

Cartesian product In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is : A\ti ...

and the

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

. For example, the

, a graph whose vertices are squares of a

chessboard A chessboard is a 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 play, the bo ...

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

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 that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...

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. The gra ...

at most six. This result has been used to prove that planar graphs have bounded

queue number In the mathematical field of graph theory, the queue number of a graph is a graph invariant defined analogously to stack number (book thickness) using first-in first-out (queue) orderings in place of last-in first-out (stack) orderings. Defin ...

, small

universal graph In mathematics, a universal graph is an infinite graph that contains ''every'' finite (or at-most-countable) graph as an induced subgraph. A universal graph of this type was first constructed by Richard Rado and is now called the Rado graph or ...

s and concise adjacency labeling schemes, and bounded nonrepetitive chromatic number and centered chromatic number. This product structure can be found in

linear time In 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 performed by ...

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

genus Genus ( plural genera ) is a taxonomic rank used in the biological classification of extant taxon, living and fossil organisms as well as Virus classification#ICTV classification, viruses. In the hierarchy of biological classification, genus com ...

, graphs with a

forbidden minor In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden ...

that is an

apex graph In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph. It is ''an'' apex, not ''the'' apex because an apex graph may have mo ...

, bounded-degree graphs with any forbidden minor, and k-planar graphs. The

clique number In the mathematical area of 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 comple ...

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 The twin-width of an undirected graph is a natural number associated with the graph, used to study the parameterized complexity of graph algorithms. Intuitively, it measures how similar the graph is to a cograph, a type of graph that can be reduced ...

, and in addition one of them has bounded degree, then their strong product also has bounded twin-width. A

leaf power In the mathematical area of graph theory, a -leaf power of a tree is a graph whose vertices are the leaves of and whose edges connect pairs of leaves whose distance in is at most . That is, is an induced subgraph of the graph power , induce ...

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.

References

{{Reflist Graph products