Uncategorized | Theory Sublime

Archive for the ‘Uncategorized’ Category

A directed graph $G$ is a tuple $G=(V(G), E(G))$ where $V$ is a finite nonempty set called the set of vertices of $G$ and $E$ is a finite subset of $V \times V$ called the set of arcs of $G$ . A graph is called undirected, if its arcs are not ordered pairs but two-element sets of vertices.

For undirected graphs $G$ and $H$ , define $G \boxtimes H$ as the graph with $V(G \boxtimes H) = V(G) \times V(H)$ and edge set defined as follows: $(uv, wx)$ is an edge in $G \boxtimes H$ iff $u=w$ or $(u,w)$ is an edge in $G$ , and $v=x$ or $(v,x)$ is an edge in $H$ . This operation is called the Strong Product (aka Shannon product) of graphs.

Strong product of two edges

For undirected graphs $G$ and $H$ , define $G \times H$ as the graph with vertex set $V(G \times H) = V(G) \times V(H)$ and edge set defined as follows: $(uv, wx)$ is an edge in $G \times H$ iff $(u,w)$ is an edge in $G$ , and $(v,w)$ is an edge in $H$ . 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 $G$ and $H$ , define $G \circ H$ as the graph with the vertex set $V( G \circ H ) = V(G) \circ V(H)$ and edge set defined as follows: $(uv, wx)$ is an edge in $G \circ H$ iff either $(u,w)$ is an edge in $G$ or $(v,x)$ is an edge in $H$ . This is called the OR Product (aka Sperner product) of graphs.

For undirected graphs $G$ and $H$ , define $G \Box H$ as the graph with vertex set $V(G \Box H) = V(G) \times V(H)$ and edge set defined as follows: $(uv,wx)$ is an edge in $G \Box H$ iff either $u=w$ and $(v,x)$ is an edge in $H$ or $(u,w)$ is an edge in $G$ and $v=x$ . This is known as the Cartesian Product of graphs.