In graph theory, a connected graph G is said to be k-vertex-connected (or k-connected) if it has more than k vertices and remains connected whenever fewer than k vertices are removed.
The vertex-connectivity, or just connectivity, of a graph is the largest k for which the graph is k-vertex-connected.
A graph (other than a complete graph) has connectivity k if k is the size of the smallest subset of vertices such that the graph becomes disconnected if you delete them. [1] In complete graphs, there is no subset whose removal would disconnect the graph. Some sources modify the definition of connectivity to handle this case, by defining it as the size of the smallest subset of vertices whose deletion results in either a disconnected graph or a single vertex. For this variation, the connectivity of a complete graph is . [2]
An equivalent definition is that a graph with at least two vertices is k-connected if, for every pair of its vertices, it is possible to find k vertex-independent paths connecting these vertices; see Menger's theorem ( Diestel 2005 , p. 55). This definition produces the same answer, n − 1, for the connectivity of the complete graph Kn. [1] Clearly the complete graph with n vertices has connectivity n − 1 under this definition.
A 1-connected graph is called connected; a 2-connected graph is called biconnected. A 3-connected graph is called triconnected.
Every graph decomposes into a tree of 1-connected components. 1-connected graphs decompose into a tree of biconnected components. 2-connected graphs decompose into a tree of triconnected components.
The 1-skeleton of any k-dimensional convex polytope forms a k-vertex-connected graph (Balinski's theorem). [3] As a partial converse, Steinitz's theorem states that any 3-vertex-connected planar graph forms the skeleton of a convex polyhedron.
The vertex-connectivity of an input graph G can be computed in polynomial time in the following way [4] consider all possible pairs of nonadjacent nodes to disconnect, using Menger's theorem to justify that the minimal-size separator for is the number of pairwise vertex-independent paths between them, encode the input by doubling each vertex as an edge to reduce to a computation of the number of pairwise edge-independent paths, and compute the maximum number of such paths by computing the maximum flow in the graph between and with capacity 1 to each edge, noting that a flow of in this graph corresponds, by the integral flow theorem, to pairwise edge-independent paths from to .
Let k≥2.
The cycle space of a -connected graph is generated by its non-separating induced cycles. [6]
A graph with at least vertices is called -linked if there are disjoint paths for any sequences and of distinct vertices. Every -linked graph is -connected graph, but not necessarily -connected. [7]
If a graph is -connected and has average degree of at least , then it is -linked. [8]
In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph.
In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. The computational problems of determining whether such paths and cycles exist in graphs are NP-complete; see Hamiltonian path problem for details.
In graph theory, a component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph. The components of any graph partition its vertices into disjoint sets, and are the induced subgraphs of those sets. A graph that is itself connected has exactly one component, consisting of the whole graph. Components are sometimes called connected components.
In graph theory, a branch of mathematics, the (binary) cycle space of an undirected graph is the set of its even-degree subgraphs.
This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.
In graph theory, an Eulerian trail is a trail in a finite graph that visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. The problem can be stated mathematically like this:
In the mathematical discipline of graph theory, Menger's theorem says that in a finite graph, the size of a minimum cut set is equal to the maximum number of disjoint paths that can be found between any pair of vertices. Proved by Karl Menger in 1927, it characterizes the connectivity of a graph. It is generalized by the max-flow min-cut theorem, which is a weighted, edge version, and which in turn is a special case of the strong duality theorem for linear programs.
In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases the graph's number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. For a connected graph, a bridge can uniquely determine a cut. A graph is said to be bridgeless or isthmus-free if it contains no bridges.
In graph theory, the degree of a vertex of a graph is the number of edges that are incident to the vertex; in a multigraph, a loop contributes 2 to a vertex's degree, for the two ends of the edge. The degree of a vertex is denoted or . The maximum degree of a graph is denoted by , and is the maximum of 's vertices' degrees. The minimum degree of a graph is denoted by , and is the minimum of 's vertices' degrees. In the multigraph shown on the right, the maximum degree is 5 and the minimum degree is 0.
In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network.
In graph theory, the Kneser graphK(n, k) (alternatively KGn,k) is the graph whose vertices correspond to the k-element subsets of a set of n elements, and where two vertices are adjacent if and only if the two corresponding sets are disjoint. Kneser graphs are named after Martin Kneser, who first investigated them in 1956.
In graph theory, a factor of a graph G is a spanning subgraph, i.e., a subgraph that has the same vertex set as G. A k-factor of a graph is a spanning k-regular subgraph, and a k-factorization partitions the edges of the graph into disjoint k-factors. A graph G is said to be k-factorable if it admits a k-factorization. In particular, a 1-factor is a perfect matching, and a 1-factorization of a k-regular graph is a proper edge coloring with k colors. A 2-factor is a collection of cycles that spans all vertices of the graph.
In graph theory, a connected graph is k-edge-connected if it remains connected whenever fewer than k edges are removed.
In graph theory, a biconnected graph is a connected and "nonseparable" graph, meaning that if any one vertex were to be removed, the graph will remain connected. Therefore a biconnected graph has no articulation vertices.
In graph theory, a peripheral cycle in an undirected graph is, intuitively, a cycle that does not separate any part of the graph from any other part. Peripheral cycles were first studied by Tutte (1963), and play important roles in the characterization of planar graphs and in generating the cycle spaces of nonplanar graphs.
In graph theory, a branch of mathematics, a clique sum is a way of combining two graphs by gluing them together at a clique, analogous to the connected sum operation in topology. If two graphs G and H each contain cliques of equal size, the clique-sum of G and H is formed from their disjoint union by identifying pairs of vertices in these two cliques to form a single shared clique, and then deleting all the clique edges or possibly deleting some of the clique edges. A k-clique-sum is a clique-sum in which both cliques have exactly k vertices. One may also form clique-sums and k-clique-sums of more than two graphs, by repeated application of the clique-sum operation.
Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes.
In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the vertices and edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyhedral graphs are the 3-vertex-connected, planar graphs.
In the mathematics of infinite graphs, an end of a graph represents, intuitively, a direction in which the graph extends to infinity. Ends may be formalized mathematically as equivalence classes of infinite paths, as havens describing strategies for pursuit–evasion games on the graph, or as topological ends of topological spaces associated with the graph.
In graph theory, the Nash-Williams theorem is a tree-packing theorem that describes how many edge-disjoint spanning trees (and more generally forests) a graph can have:
A graph G has t edge-disjoint spanning trees iff for every partition where there are at least t(k − 1) crossing edges (Tutte 1961, Nash-Williams 1961).
