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 $G_{1}$ and $G_{2}$ is denoted $G_{1}+G_{2}$ ,^[1]^[2] $G_{1}\vee G_{2}$ ,^[3] 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:^[1]^[2]^[3]

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).^[4]
Star graph: $S_{n+1}={\overline {K}}_{n}+K_{1}$ (join of a $n$ vertex empty graph and a single vertex).^[4]
Fan graph: $F_{m,n}=P_{n}+{\overline {K}}_{m}$ (join of a path graph with a empty graph).^[4]
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).^[4]

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).^[5]

Chromatic number

The chromatic number of the join satisfies:

\chi (G_{1}+G_{2})=\chi (G_{1})+\chi (G_{2})

.

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.^[6]

$G_{1}+G_{2}$ is color critical if and only if $G_{1}$ and $G_{2}$ are both color critical.^[5]

Join (graph theory)

Definition

Examples

Properties

Basic properties

Chromatic number

See also

References

External links

Related Articles