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 GraphSearch.
Concept
Graph product
Summary
In graph theory, a graph product is a binary operation on graphs. Specifically, it is an operation that takes two graphs G_1 and G_2 and produces a graph H with the following properties:
The vertex set of H is the Cartesian product V(G_1) × V(G_2), where V(G_1) and V(G_2) are the vertex sets of G_1 and G_2, respectively.
Two vertices (a_1,a_2) and (b_1,b_2) of H are connected by an edge, iff a condition about a_1, b_1 in G_1 and a_2, b_2 in G_2 is fulfilled.
The graph products differ in what exactly this condition is. It is always about whether or not the vertices a_n, b_n in G_n are equal or connected by an edge.
The terminology and notation for specific graph products in the literature varies quite a lot; even if the following may be considered somewhat standard, readers are advised to check what definition a particular author uses for a graph product, especially in older texts.
The following table shows the most common graph products, with denoting "is connected by an edge to", and denoting non-connection. The operator symbols listed here are by no means standard, especially in older papers.
In general, a graph product is determined by any condition for that can be expressed in terms of and .
Let be the complete graph on two vertices (i.e. a single edge). The product graphs , , and look exactly like the graph representing the operator. For example, is a four cycle (a square) and is the complete graph on four vertices.
The notation for lexicographic product serves as a reminder that this product is not commutative. The resulting graph looks like substituting a copy of for every vertex of .
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.