Join (graph theory)

File:Join operation on graphs C4 and K4.svg

Join operation on graphs C₄ (blue) and K₄ (red).

In graph theory, the join operation is a graph operation that combines two graphs by connecting every vertex of one graph to every vertex of the other. The join of two graphs $G_1$ and $G_2$ is denoted $G_1+G_2$, $G_1\vee G_2$, or $G_1\mathrm{\nabla }{G}_2$.

Definition

Let $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ be two disjoint graphs. The join $G_1+G_2$ is a graph with:

• Vertex set: $V(G_1+G_2)=V_1\cup V_2$
• Edge set: $E(G_1+G_2)=E_1\cup E_2\cup \{uv\mid u\in V_1,v\in V_2\}$

In other words, the join contains all vertices and edges from both original graphs, plus new edges connecting every vertex in $G_1$ to every vertex in $G_2$.

Examples

Several well-known graph families can be constructed using the join operation.

Complete bipartite graph

$K_{m,n}={\bar{K}}_m+{\bar{K}}_n$ (join of two independent sets).

Wheel graph

$W_n=C_n+K_1$ (join of a cycle graph and a single vertex).

Star graph

$S_{n+1}={\bar{K}}_n+K_1$ (join of a $n$ vertex empty graph and a single vertex).

Fan graph

$F_{m,n}=P_n+{\bar{K}}_m$ (join of a path graph with a empty graph).

Complete graph

$K_n=K_m+K_{n-m}$ (join of two complete graphs whose orders sum to $n$).

Cograph

Cographs are formed by repeated join and disjoint union operations starting from single vertices.

Windmill graph

$D_n^{(m)}=m{K}_{n-1}+K_1$ (join of $m$ copies of the complete graph on $n-1$ vertices with a single vertex).

Properties

Basic properties

The join operation is commutative for unlabeled graphs: $G_1+G_2\cong G_2+G_1$.

If $G_1$ has $p_1$ vertices and $q_1$ edges, and $G_2$ has $p_2$ vertices and $q_2$ edges, then $G_1+G_2$ has $p_1+p_2$ vertices and $q_1+q_2+p_1{p}_2$ edges. If $p_1>0$ and $p_2>0$ then $G_1+G_2$ is connected ($K_{p_1,p_2}$ is a subgraph).

Chromatic number

The chromatic number of the join satisfies:

$\chi (G_1+G_2)=\chi (G_1)+\chi (G_2)$.

File:Sulanke Earth-Moon map.svg

The join of a 5-cycle and a 6-clique and its representation as an Earth–Moon map

This property holds because vertices from $G_1$ and $G_2$ must use different colors (as they are all adjacent to each other), and within each original graph, the minimum coloring is preserved. It was used in a 1974 construction by Thom Sulanke related to the Earth–Moon problem of coloring graphs of thickness two. Sulanke observed that the join $C_5+K_6$ is a thickness-two graph requiring nine colors, still the largest number of colors known to be needed for this problem.

$G_1+G_2$ is color critical if and only if $G_1$ and $G_2$ are both color critical.

See also

• Disjoint union of graphs
• Graph minor
• Join (topology)