Concept

Disjoint union of graphs

In graph theory, a branch of mathematics, the disjoint union of graphs is an operation that combines two or more graphs to form a larger graph. It is analogous to the disjoint union of sets, and is constructed by making the vertex set of the result be the disjoint union of the vertex sets of the given graphs, and by making the edge set of the result be the disjoint union of the edge sets of the given graphs. Any disjoint union of two or more nonempty graphs is necessarily disconnected. The disjoint union is also called the graph sum, and may be represented either by a plus sign or a circled plus sign: If and are two graphs, then or denotes their disjoint union. Certain special classes of graphs may be represented using disjoint union operations. In particular: The forests are the disjoint unions of trees. The cluster graphs are the disjoint unions of complete graphs. The 2-regular graphs are the disjoint unions of cycle graphs. More generally, every graph is the disjoint union of connected graphs, its connected components. The cographs are the graphs that can be constructed from single-vertex graphs by a combination of disjoint union and complement operations.

Official source

https://en.wikipedia.org/wiki/Disjoint_union_of_graphs

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related lectures (5)

Prim's and Kruskal's Algorithms

Explores Prim's and Kruskal's algorithms for finding minimum spanning trees in a graph, covering their correctness, implementation, and analysis.

Properties of X/G

Explores the properties of the quotient space X/G when X is compact and sometimes separated.

Algorithms: Union Find and Minimum Spanning Trees

Discusses Union-Find data structures and Minimum Spanning Trees, covering algorithms and their applications in network design and optimization.

Related publications (2)

Spectral clustering in birthday paradox time

Given a vertex in a (𝑘,𝜑,𝜖)-clusterable graph, i.e. a graph whose vertex set can be partitioned into a disjoint union of 𝜑-expanders of size ≈𝑛/𝑘 with outer conductance bounded by 𝜖, can one quickly tell which cluster it belongs to? This is a classical question going back to the expansion testing problem of Goldreich and Ron’11 (the case of 𝑘 =2) that has received a lot of attention in the literature. For 𝑘 =2 a sample of ≈𝑛1/2+𝑂⁢(𝜖/𝜑2) logarithmic length walks from a given vertex approximately determines

Society for Industrial and Applied Mathematics2026

Polar cographs

Dominique de Werra

Polar graphs are a natural extension of some classes of graphs like bipartite graphs, split graphs and complements of bipartite graphs. A graph is (s,k)-polar if there exists a partition A,B of its vertex set such that A induces a complete s-partite graph (i.e., a collection of at most s disjoint stable sets with complete links between all sets) and B a disjoint union of at most k cliques (i.e., the complement of a complete k-partite graph).\ Recognizing a polar graph is known to be NP-complete. So these g

2005

Related people (2)

Weronika Wrzos-Kaminska

Oliver Janzer

Teaching & PhD PhD Students Rik Sarkar Courses Algebraic methods in combinatorics MATH-526 In this course we study how algebraic methods can be used to solve problems in combinatorics. The main tools used are from linear algebra and from the theory of polynomials. Graph theory MATH-360 The course aims to introduce the basic concepts and results of modern Graph Theory. Awards European Prize in Combinatorics 2025 British Combinatorial Committee PhD Prize 2022 Smith-Knight

Related concepts (2)

Complement graph

In the mathematical field of graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two distinct vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and removes all the edges that were previously there. The complement is not the set complement of the graph; only the edges are complemented. Let G = (V, E) be a simple graph and let K consist of all 2-element subsets of V.

Cograph

In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K1 and is closed under complementation and disjoint union. Cographs have been discovered independently by several authors since the 1970s; early references include , , , and . They have also been called D*-graphs, hereditary Dacey graphs (after the related work of James C.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.