## Introduction to graph products

A directed graph is a tuple where is a finite nonempty set called the set of vertices of and is a finite subset of called the set of arcs of . A graph is called undirected, if its arcs are not ordered pairs but two-element sets of vertices.

For undirected graphs and , define as the graph with and edge set defined as follows: is an edge in iff or is an edge in , and or is an edge in . This operation is called the Strong Product (aka Shannon product) of graphs.

For undirected graphs and , define as the graph with vertex set and edge set defined as follows: is an edge in iff is an edge in , and is an edge in . This operation is called the Direct Product (aka Categorical product) of graphs.

For directed graphs and , define as the graph with the vertex set and edge set defined as follows: is an edge in iff either is an edge in or is an edge in . This is called the OR Product (aka Sperner product) of graphs.

For undirected graphs and , define as the graph with vertex set and edge set defined as follows: is an edge in iff either and is an edge in or is an edge in and . This is known as the Cartesian Product of graphs.

I will discuss more about these interesting products later.

## Leave a Reply