Archive for the ‘Uncategorized’ Category
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.

Strong product of two edges
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.

Direct product of two arcs, each with loops on both its vertices
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.