Join (graph theory)

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}\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}={\overline {K}}_{m}+{\overline {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}={\overline {K}}_{n}+K_{1}$ (join of a $n$ vertex empty graph and a single vertex).

Fan graph

$F_{m,n}=P_{n}+{\overline {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)}=mK_{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})$.

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.

External links

• Weisstein, Eric W. "Graph Join". MathWorld.