Disjoint union of graphs

Last updated
A cluster graph, the disjoint union of complete graphs Equivalentie.svg
A cluster graph, the disjoint union of complete 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.

Graph theory study of graphs, which are mathematical structures used to model pairwise relations between objects

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices which are connected by edges. A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges, then called arrows, link two vertices asymmetrically; see Graph for more detailed definitions and for other variations in the types of graph that are commonly considered. Graphs are one of the prime objects of study in discrete mathematics.

Graph (discrete mathematics) mathematical structure; representation of a set of objects where some pairs of the objects are connected by links

In mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called vertices and each of the related pairs of vertices is called an edge. Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study in discrete mathematics.

In set theory, the disjoint union of a family of sets is a modified union operation that indexes the elements according to which set they originated in. Or slightly different from this, the disjoint union of a family of subsets is the usual union of the subsets which are pairwise disjoint – disjoint sets means they have no element in common.

Contents

Notation

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. [1]

Certain special classes of graphs may be represented using disjoint union operations. In particular:

Tree (graph theory) undirected, connected and acyclic graph

In mathematics, and, more specifically, in graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path. Every acyclic connected graph is a tree, and vice versa. A forest is a disjoint union of trees, or equivalently an acyclic graph that is not necessarily connected.

Cluster graph

In graph theory, a branch of mathematics, a cluster graph is a graph formed from the disjoint union of complete graphs. Equivalently, a graph is a cluster graph if and only if it has no three-vertex induced path; for this reason, the cluster graphs are also called P3-free graphs. They are the complement graphs of the complete multipartite graphs and the 2-leaf powers.

Complete graph simple undirected graph in which every pair of distinct vertices is connected by a unique edge

In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is connected by a pair of unique edges.

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. [5]

Cograph a type of graph, formed recursively by complementation and disjoint union operations

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.

Complement graph

In 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. It is not, however, the set complement of the graph; only the edges are complemented.

Related Research Articles

Bipartite graph graph of two sets in which every vertex in one set is connected to at least one in the other

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets and such that every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

In graph theory, a branch of mathematics, the (binary) cycle space of an undirected graph is the set of its Eulerian subgraphs.

This is a glossary of graph theory terms. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by edges.

Turán graph graph

The Turán graphT(n,r) is a complete multipartite graph formed by partitioning a set of n vertices into r subsets, with sizes as equal as possible, and connecting two vertices by an edge if and only if they belong to different subsets. The graph will have subsets of size , and subsets of size . That is, it is a complete r-partite graph

Clique (graph theory) subset of the vertices of a node-link graph that are all adjacent to each other

In the mathematical area of graph theory, a clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent; that is, its induced subgraph is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph is NP-complete, but despite this hardness result, many algorithms for finding cliques have been studied.

Bridge (graph theory) An edge in a node-link graph whose removal would disconnect the graph

In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases its number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. A graph is said to be bridgeless or isthmus-free if it contains no bridges.

Circuit rank the minimum number of edges to remove from a graph to eliminate all its cycles

In graph theory, a branch of mathematics, the circuit rank, cyclomatic number, cycle rank, or nullity of an undirected graph is the minimum number of edges that must be removed from the graph to break all its cycles, making it into a tree or forest. Alternatively, it can be interpreted as the number of independent cycles in the graph. Unlike the corresponding feedback arc set problem for directed graphs, the circuit rank r is easily computed using the formula

Cartesian product of graphs

In graph theory, the Cartesian productGH of graphs G and H is a graph such that

In graph theory, a connected graph is k-edge-connected if it remains connected whenever fewer than k edges are removed.

Kőnigs theorem (graph theory) theorem showing that maximum matching and minimum vertex cover are equivalent for bipartite graphs

In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig (1931), describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.

Hypercube graph

In graph theory, the hypercube graphQn is the graph formed from the vertices and edges of an n-dimensional hypercube. For instance, the cubical graph Q3 is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. Qn has 2n vertices, 2n−1n edges, and is a regular graph with n edges touching each vertex.

Neighbourhood (graph theory) vertices adjacent to a given vertex in a node-link graph

In graph theory, an adjacent vertex of a vertex v in a graph is a vertex that is connected to v by an edge. The neighbourhood of a vertex v in a graph G is the subgraph of G induced by all vertices adjacent to v, i.e., the graph composed of the vertices adjacent to v and all edges connecting vertices adjacent to v. For example, in the image to the right, the neighbourhood of vertex 5 consists of vertices 1, 2 and 4 and the edge connecting vertices 1 and 2.

Threshold graph

In graph theory, a threshold graph is a graph that can be constructed from a one-vertex graph by repeated applications of the following two operations:

  1. Addition of a single isolated vertex to the graph.
  2. Addition of a single dominating vertex to the graph, i.e. a single vertex that is connected to all other vertices.
Trivially perfect graph

In graph theory, a trivially perfect graph is a graph with the property that in each of its induced subgraphs the size of the maximum independent set equals the number of maximal cliques. Trivially perfect graphs were first studied by but were named by Golumbic (1978); Golumbic writes that "the name was chosen since it is trivial to show that such a graph is perfect." Trivially perfect graphs are also known as comparability graphs of trees, arborescent comparability graphs, and quasi-threshold graphs.

In matroid theory, a field within mathematics, a gammoid is a certain kind of matroid, describing sets of vertices that can be reached by vertex-disjoint paths in a directed graph.

In graph theory, the modular decomposition is a decomposition of a graph into subsets of vertices called modules. A module is a generalization of a connected component of a graph. Unlike connected components, however, one module can be a proper subset of another. Modules therefore lead to a recursive (hierarchical) decomposition of the graph, instead of just a partition.

Locally linear graph

In graph theory, a locally linear graph is an undirected graph in which the neighborhood of every vertex is an induced matching. That is, for every vertex , every neighbor of should be adjacent to exactly one other neighbor of . Equivalently, every edge of such a graph belongs to a unique triangle . Locally linear graphs have also been called locally matched graphs.

References

  1. ↑ Rosen, Kenneth H. (1999), Handbook of Discrete and Combinatorial Mathematics, Discrete Mathematics and Its Applications, CRC Press, p. 515, ISBN   9780849301490
  2. ↑ Grossman, Jerrold W. (1990), Discrete Mathematics: An Introduction to Concepts, Methods, and Applications, Macmillan, p. 627, ISBN   9780023483318
  3. ↑ Cluster graphs, Information System on Graph Classes and their Inclusions, accessed 2016-06-26.
  4. ↑ Chartrand, Gary; Zhang, Ping (2013), A First Course in Graph Theory, Dover Books on Mathematics, Courier Corporation, p. 201, ISBN   9780486297309
  5. ↑ Corneil, D. G.; Lerchs, H.; Stewart Burlingham, L. (1981), "Complement reducible graphs", Discrete Applied Mathematics , 3 (3): 163–174, doi:10.1016/0166-218X(81)90013-5, MR   0619603
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.