Graph Union

The union  of graphs  and  with disjoint point sets  and  and edge sets  and  is the graph with  and  (Harary 1994, p. 21; Gross and Yellen 2006, p. 85).

When the vertices and edges of  and  are considered distinct regardless of their labels, the operation is sometimes known as the graph disjoint union in order to distinguish it from the graph union operation that merges vertices and edges with shared labels when taking the unions of edges and vertices in  and .

The Wolfram Language function GraphUnion[g1, g2] takes the graph union by merging labeled vertices and edges, while GraphDisjointUnion[g1, g2, ...] treats vertices and edges in the components as distinct regardless of their labels.

The graph disjoint union of  copies of a graph  is commonly denoted  (Harary 1990, p. 21).

REFERENCES

Gross, J. T. and Yellen, J. Graph Theory and Its Applications, 2nd ed. Boca Raton, FL: CRC Press, 2006.

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 21, 1994.

Skiena, S. "Unions and Intersections." §4.1.1 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 129-131, 1990.