Join (graph theory)

In graph theory, the join operation is a binary operation that combines two graphs by connecting every vertex of one graph to every vertex of the other. The join of two graphs ${\displaystyle G_{1}}$ and ${\displaystyle G_{2}}$ is denoted ${\displaystyle G_{1}\nabla G_{2}}$ or ${\displaystyle G_{1}+G_{2}}$.

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}\nabla G_{2}}$ is a graph with:^[1]

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

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

• Complete bipartite graph: ${\displaystyle K_{m,n}={\overline {K}}_{m}\nabla {\overline {K}}_{n}}$ (join of two independent sets)
• Wheel graph: ${\displaystyle W_{n}=C_{n}\nabla K_{1}}$ (join of a cycle graph and a single vertex)
• Fan graph: ${\displaystyle F_{n}=P_{n}\nabla 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
• Friendship graph: ${\displaystyle Fr_{n}}$ for ${\displaystyle n=2t+1}$ is obtained by joining ${\displaystyle K_{1}}$ to ${\displaystyle t}$ disjoint copies of ${\displaystyle K_{2}}$^[2]

The join operation is commutative for unlabeled graphs: ${\displaystyle G_{1}\nabla G_{2}\cong G_{2}\nabla 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}\nabla G_{2}}$ has:

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

The diameter of ${\displaystyle G_{1}\nabla G_{2}}$ is at most 2 (provided both graphs are non-empty).^[2]

The chromatic number of the join satisfies:

${\displaystyle \chi (G_{1}\nabla G_{2})=\chi (G_{1})+\chi (G_{2})}$.

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.

The locating chromatic number ${\displaystyle \chi _{L}(G)}$ is a refinement of the chromatic number where vertices with the same color must be distinguishable by their distance to color classes. For the join operation, when ${\displaystyle G_{1}}$ and ${\displaystyle G_{2}}$ are connected graphs with diameter at most 2:^[2]

${\displaystyle \chi _{L}(G_{1}+G_{2})=\chi _{L}(G_{1})+\chi _{L}(G_{2})}$

This result extends to specific graph families. For example, for the wheel graph ${\displaystyle W_{n}=K_{1}+C_{n}}$:^[2]

${\displaystyle \chi _{L}(W_{n})=1+\chi _{L}(C_{n})}$

Unlike the chromatic number, the locating chromatic number of joins does not always decompose additively. For instance, ${\displaystyle \chi _{L}(P_{10})=3}$ but ${\displaystyle \chi _{L}(P_{10}+P_{10})=8\neq 3+3}$.

For specific graph families:

• ${\displaystyle \chi _{L}(K_{m}\nabla P_{n})}$ has been determined for all values of ${\displaystyle m}$ and ${\displaystyle n}$
• ${\displaystyle \chi _{L}(K_{m}\nabla C_{n})}$ has been determined, including the special case of wheel graphs ${\displaystyle W_{n}=K_{1}\nabla C_{n}}$
• ${\displaystyle \chi _{L}(C_{m}\nabla C_{n})}$ has been computed for all cycle pairs

Certain graph joins produce completely extendable graphs. For instance, if ${\displaystyle G}$ is a completely extendable graph, then ${\displaystyle G\nabla K_{n}}$ is also completely extendable with the same order of extension as ${\displaystyle G}$.^[1]

In computer networking, the join operation models the complete integration of two separate networks, where every node in one network can directly communicate with every node in the other. This structure is relevant during corporate network mergers or cloud computing integration processes.^[1]

The join operation models full collaboration between two distinct groups, such as when two research teams merge and all members from one team establish connections with all members of the other team.

In parallel and distributed computing systems, the graph join represents scenarios where any task from one set can be assigned to any processor from another set, providing a framework for analyzing optimal task scheduling strategies.^[1]

• Graph operations
• Graph product
• Complete bipartite graph
• Cartesian product of graphs

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