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})

.

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

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

References

^ ^a ^b ^c Bollobás, Béla (1998). Modern Graph Theory. Graduate Texts in Mathematics. Springer. p. 7. ISBN 0-387-98491-7.
^ ^a ^b ^c Beineke, Lowell; Wilson, Robin; Cameron, Peter. "Introduction". In Beineke, Lowell W.; Wilson, Robin J. (eds.). Topics in Algebraic Graph Theory. Encyclopedia of Mathematics and Its Applications. Vol. 102. Cambridge University Press. p. 6. ISBN 0-521-80197-4.
^ ^a ^b ^c Bondy, J. A.; Murty, U. S. R. (1976). Graph Theory with Applications. Elsevier. p. 58.
^ ^a ^b ^c ^d Weisstein, Eric W. "Graph Join". mathworld.wolfram.com. Retrieved 2025-10-30.
^ ^a ^b West, Douglas Brent (2001). Introduction to graph theory (2. ed.). Upper Saddle River, NJ: Prentice Hall. ISBN 978-0130144003.
^ Gethner, Ellen (2018). "To the moon and beyond". In Gera, Ralucca; Haynes, Teresa W.; Hedetniemi, Stephen T. (eds.). Graph theory—favorite conjectures and open problems. 2. Problem Books in Mathematics. Cham: Springer. pp. 115–133. ISBN 978-3-319-97684-6. MR 3930641.

External links

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

[bollobas-1] Bollobás, Béla (1998). Modern Graph Theory. Graduate Texts in Mathematics. Springer. p. 7. ISBN 0-387-98491-7.

[TAGT-2] Beineke, Lowell; Wilson, Robin; Cameron, Peter. "Introduction". In Beineke, Lowell W.; Wilson, Robin J. (eds.). Topics in Algebraic Graph Theory. Encyclopedia of Mathematics and Its Applications. Vol. 102. Cambridge University Press. p. 6. ISBN 0-521-80197-4.

[bondy-murty-3] Bondy, J. A.; Murty, U. S. R. (1976). Graph Theory with Applications. Elsevier. p. 58.

[:1-4] Weisstein, Eric W. "Graph Join". mathworld.wolfram.com. Retrieved 2025-10-30.

[:0-5] West, Douglas Brent (2001). Introduction to graph theory (2. ed.). Upper Saddle River, NJ: Prentice Hall. ISBN 978-0130144003.

[6] Gethner, Ellen (2018). "To the moon and beyond". In Gera, Ralucca; Haynes, Teresa W.; Hedetniemi, Stephen T. (eds.). Graph theory—favorite conjectures and open problems. 2. Problem Books in Mathematics. Cham: Springer. pp. 115–133. ISBN 978-3-319-97684-6. MR 3930641.

[1]