TOPICS
Search

Graph Disjoint Union

The graph disjoint union of graphs G_1 and G_2 is obtained by replacing them, if necessary, by isomorphic copies having disjoint vertex sets, and then taking their graph union (Harary 1994, p. 21; Gross and Yellen 2006, p. 85). Thus vertices and edges from the two input graphs remain distinct even when their original vertex labels coincide, and no edges are added between the two copies.

The operation is commonly denoted G_1⊔G_2 (Gromada 2022; Bucić and Sudakov 2023, p. 544). Knuth (2024, p. 23) instead denotes it G_1 direct sum G_2. The graph disjoint union of n copies of a graph G is commonly denoted nG (Harary 1994, p. 21).

The Wolfram Language function GraphDisjointUnion[g1, g2, ...] treats vertices and edges in the input graphs as distinct regardless of their labels.

See also

Disjoint Union, Graph Join, Graph Sum, Graph Union

Explore with Wolfram|Alpha

References

Bucić, M. and Sudakov, B. "Large Independent Sets from Local Considerations." Combinatorica 43, 505-546, 2023. https://doi.org/10.1007/s00493-023-00023-w.Gromada, D. "Group-Theoretical Graph Categories." J. Algebraic Combin. 55, 591-627, 2022. https://doi.org/10.1007/s10801-021-01063-5.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.Knuth, D. E. §7.2.2.3 in The Art of Computer Programming, Vol. 4. Pre-Fascicle 7A, Dec. 5, 2024.

Referenced on Wolfram|Alpha

Graph Disjoint Union

Cite this as:

Weisstein, Eric W. "Graph Disjoint Union." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GraphDisjointUnion.html

Subject classifications