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. The join of two graphs and is denoted,, or.

Definition

Let and be two disjoint graphs. The join is a graph with:
  • Vertex set:
  • Edge set:
In other words, the join contains all vertices and edges from both original graphs, plus new edges connecting every vertex in to every vertex in.

Examples

Several well-known graph families can be constructed using the join operation.
;Complete bipartite graph
;Wheel graph
;Star graph
;Fan graph
;Complete graph
;Cograph
;Windmill graph

Properties

Basic properties

The join operation is commutative for unlabeled graphs:.
If has vertices and edges, and has vertices and edges, then has vertices and edges. If and then is connected.

Chromatic number

The chromatic number of the join satisfies:
This property holds because vertices from and must use different colors, 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 is a thickness-two graph requiring nine colors, still the largest number of colors known to be needed for this problem.
is color critical if and only if and are both color critical.