Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Strong product of graphs
Summary
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.
The strong product G ⊠ H of graphs G and H is a graph such that
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.
Every planar graph is a subgraph of a strong product of a path and a graph of treewidth 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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.