Join (graph theory)

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.^[1][2][3] The join of two graphs ${\displaystyle G_{1}}$ and ${\displaystyle G_{2}}$ is denoted ${\displaystyle G_{1}+G_{2}}$,^[1][2] ${\displaystyle G_{1}\vee G_{2}}$,^[3] or ${\displaystyle G_{1}\nabla G_{2}}$.

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

Definition

Let ${\displaystyle G_{1}=(V_{1},E_{1})}$ and ${\displaystyle G_{2}=(V_{2},E_{2})}$ be two disjoint graphs. The join ${\displaystyle G_{1}+G_{2}}$ is a graph with:^[1][2][3]

• Vertex set: ${\displaystyle V(G_{1}+G_{2})=V_{1}\cup V_{2}}$
• Edge set: ${\displaystyle 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 ${\displaystyle G_{1}}$ to every vertex in ${\displaystyle G_{2}}$.

Examples

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

Complete bipartite graph

${\displaystyle K_{m,n}={\overline {K}}_{m}+{\overline {K}}_{n}}$ (join of two independent sets)

Wheel graph

${\displaystyle W_{n}=C_{n}+K_{1}}$ (join of a cycle graph and a single vertex)

Fan graph

${\displaystyle F_{n}=P_{n}+K_{1}}$ (join of a path graph and a single vertex)

Complete graph

Any complete graph can be expressed as the join of smaller complete graphs

Cograph

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

Properties

Basic properties

The join operation is commutative for unlabeled graphs: ${\displaystyle G_{1}+G_{2}\cong G_{2}+G_{1}}$.

If ${\displaystyle G_{1}}$ has ${\displaystyle p_{1}}$ vertices and ${\displaystyle q_{1}}$ edges, and ${\displaystyle G_{2}}$ has ${\displaystyle p_{2}}$ vertices and ${\displaystyle q_{2}}$ edges, then ${\displaystyle G_{1}+G_{2}}$ has:

• Vertices: ${\displaystyle p_{1}+p_{2}}$
• Edges: ${\displaystyle q_{1}+q_{2}+p_{1}p_{2}}$

Chromatic number

The chromatic number of the join satisfies:

${\displaystyle \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 ${\displaystyle G_{1}}$ and ${\displaystyle 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 ${\displaystyle 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.^[4]