Graph join
In the mathematical field of graph theory, the graph join (also called the sum of graphs in some literature, particularly in Spanish-language sources) is a binary operation on graphs. The operation consists of taking the union of the vertex sets and the edge sets of both graphs, plus the set of edges that connect the vertices of the first graph with the vertices of the second graph. It is a commutative operation for unlabeled graphs.
Formal definition
Let G1 = (V1, E1) and G2 = (V2, E2) be two graphs. The join of G1 and G2, denoted G1 + G2 or G1 ∇ G2, is the graph G′ = (V′, E′) where:
- V′ = V1 ∪ V2
- E′ = E1 ∪ E2 ∪ { {x, y} : x ∈ V1, y ∈ V2 }
In other words, the join operation takes the disjoint union of the two graphs and adds all edges between vertices of the first graph and vertices of the second graph.[1]
Examples
Notable examples of graph joins include:
- Wheel graphs Wn can be defined as the join of a singleton graph K1 and a cycle graph Cn: Wn = K1 + Cn.
- The join of a complete graph Kn and a single isolated vertex K1 results in the complete graph Kn+1: Kn + K1 = Kn+1.
Properties
The graph join operation has the following properties:
- Commutativity: For unlabeled graphs, G1 + G2 ≅ G2 + G1.[1]
- Connectivity: The join of any two nonempty graphs is always a connected graph.[2]
- The join of two graphs with n and m vertices respectively has n + m vertices and |E1| + |E2| + nm edges.
Applications
The set-theoretic union approach used in graph join operations has found applications in various fields:
- In artificial intelligence and mechanistic interpretability, similar set-theoretic union methods are employed to merge knowledge graphs and construct computational graphs that trace information flow in large language models. These methods combine vertex and edge sets from multiple graphs to create unified attribution graphs that explain model behaviors.[3]
Set-theoretic resolution (Union)
When graphs are represented as a matrix of n columns, where each column represents a vertex and the n rows of each column represent the edges (memory address of the vertex to which it points), this matrix being not necessarily square, and having all the graphs to be joined in a list, an algorithm using a set-theoretic union approach can be described as follows:
- Traverse the list of graphs looking for the graph with the largest number of vertices. If there is more than one graph with the same maximum number of vertices, choose by order of entry.
- Once located at the graph with the largest number of vertices, create a new graph called GraphSum as an identical copy of the first selected graph (also creating it as a matrix).
- Move to the next graph with the largest number of vertices and locate its first vertex V (the first column of the matrix). Simultaneously, take GraphSum and search for V in its vertices. If that vertex is not found in GraphSum, add the entire column (the vertex with its edges) to GraphSum. However, if V is found in GraphSum, only add the edges of V that are not already in that vertex of GraphSum.
- Once all vertices of the graph being added to GraphSum have been traversed, select the next graph (by order of number of vertices) and repeat step 3 until all graphs in the list have been joined.
See also
References
- ↑ 1.0 1.1 Harary, Frank (1969). Graph Theory. Reading, MA: Addison-Wesley. ISBN 978-0-201-02787-7. Search this book on
- ↑ Chartrand, Gary; Lesniak, Linda; Zhang, Ping (2010). Graphs & Digraphs (5th ed.). Chapman and Hall/CRC. ISBN 978-1-4398-0381-8 Check
|isbn=value: checksum (help). Search this book on
- ↑ Ameisen, Emmanuel (2025). "Circuit Tracing: Revealing Computational Graphs in Language Models". Anthropic.
This article "Graph join" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Graph join. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
