Join (graph theory)

[[File:Join operation on graphs C4 and K4.svg|thumb|Join operation on graphs {{mvar|C{{sub|4}}}} (blue) and {{mvar|K{{sub|4}}}} (red).]]

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.<ref name="bollobas">{{cite book|first=Béla |last=Bollobás |author-link=Béla Bollobás |title=Modern Graph Theory |publisher=Springer |series=Graduate Texts in Mathematics |year=1998 |isbn=0-387-98491-7 |page=7}}</ref><ref name="TAGT">{{cite book|title=Topics in Algebraic Graph Theory |editor-first1=Lowell W. |editor-last1=Beineke |editor-first2=Robin J. |editor-last2=Wilson |publisher=Cambridge University Press |series=Encyclopedia of Mathematics and Its Applications |volume=102 |chapter=Introduction |first1=Lowell |last1=Beineke |author-link1=L. W. Beineke |first2=Robin |last2=Wilson |author-link2=Robin Wilson (mathematician) |first3=Peter |last3=Cameron |author-link3=Peter Cameron (mathematician) |isbn=0-521-80197-4 |page=6}}</ref><ref name=bondy-murty>{{cite book|title=Graph Theory with Applications|first1=J. A.|last1=Bondy|first2=U. S. R.|last2=Murty|publisher=Elsevier|year=1976|page=58}}</ref> The join of two graphs <math>G_1</math> and <math>G_2</math> is denoted <math>G_1 + G_2</math>,<ref name="bollobas"/><ref name="TAGT"/> <math>G_1\vee G_2</math>,<ref name=bondy-murty/> or <math>G_1 \nabla G_2</math>.

== Definition ==

Let <math>G_1 = (V_1, E_1)</math> and <math>G_2 = (V_2, E_2)</math> be two disjoint graphs. The '''join''' <math>G_1 + G_2</math> is a graph with:<ref name="bollobas"/><ref name="TAGT"/><ref name=bondy-murty/>

* Vertex set: <math>V(G_1 + G_2) = V_1 \cup V_2</math> * Edge set: <math>E(G_1 + G_2) = E_1 \cup E_2 \cup \{uv \mid u \in V_1, v \in V_2\}</math>

In other words, the join contains all vertices and edges from both original graphs, plus new edges connecting every vertex in <math>G_1</math> to every vertex in <math>G_2</math>.

== Examples ==

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

;Complete bipartite graph : <math>K_{m,n} = \overline{K}_m + \overline{K}_n</math> (join of two independent sets). ;Wheel graph : <math>W_n = C_n + K_1</math> (join of a cycle graph and a single vertex).<ref name=":1">{{Cite web |last=Weisstein |first=Eric W. |title=Graph Join |url=https://mathworld.wolfram.com/GraphJoin.html |access-date=2025-10-30 |website=mathworld.wolfram.com |language=en}}</ref> ;Star graph : <math>S_{n+1} = \overline{K}_n + K_1</math> (join of a <math>n</math> vertex empty graph and a single vertex).<ref name=":1" /> ;Fan graph : <math>F_{m,n} = P_n + \overline{K}_m</math> (join of a path graph with a empty graph).<ref name=":1" /> ;Complete graph : <math>K_n = K_m + K_{n-m}</math> (join of two complete graphs whose orders sum to <math>n</math>). ;Cograph : Cographs are formed by repeated join and disjoint union operations starting from single vertices. ;Windmill graph :<math>D_n^{(m)} = mK_{n-1} + K_1 </math> (join of $m$ copies of the complete graph on <math>n-1</math> vertices with a single vertex).<ref name=":1" />

== Properties ==

=== Basic properties === The join operation is commutative for unlabeled graphs: <math>G_1 + G_2 \cong G_2 + G_1</math>.

If <math>G_1</math> has <math>p_1</math> vertices and <math>q_1</math> edges, and <math>G_2</math> has <math>p_2</math> vertices and <math>q_2</math> edges, then <math>G_1 + G_2</math> has <math>p_1 + p_2</math> vertices and <math>q_1 + q_2 + p_1 p_2</math> edges. If <math>p_1>0</math> and <math>p_2>0</math> then <math>G_1 + G_2</math> is connected (<math>K_{p_1,p_2}</math> is a subgraph).<ref name=":0">{{cite book |last1=West |first1=Douglas Brent |title=Introduction to graph theory |date=2001 |publisher=Prentice Hall |location=Upper Saddle River, NJ |isbn=978-0130144003 |edition=2.}}</ref>

=== Chromatic number === The chromatic number of the join satisfies:

:<math>\chi(G_1 + G_2) = \chi(G_1) + \chi(G_2)</math>.

[[File:Sulanke Earth-Moon map.svg|thumb|The join of a 5-cycle and a 6-clique and its representation as an Earth–Moon map]] This property holds because vertices from <math>G_1</math> and <math>G_2</math> 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 <math>C_5+K_6</math> is a thickness-two graph requiring nine colors, still the largest number of colors known to be needed for this problem.<ref>{{cite book | last = Gethner | first = Ellen | author-link = Ellen Gethner | editor1-last = Gera | editor1-first = Ralucca | editor2-last = Haynes | editor2-first = Teresa W. | editor3-last = Hedetniemi | editor3-first = Stephen T. | contribution = To the moon and beyond | isbn = 978-3-319-97684-6 | location = Cham | mr = 3930641 | pages = 115–133 | publisher = Springer | series = Problem Books in Mathematics | title = Graph theory—favorite conjectures and open problems. 2 | year = 2018}}</ref>

<math>G_1 + G_2</math> is color critical if and only if <math>G_1</math> and <math>G_2</math> are both color critical.<ref name=":0" />

== References == {{reflist}}

== External links == * {{MathWorld|title=Graph Join|urlname=GraphJoin}}

Category:Graph operations Category:Graph theory