**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.

Concept# K-vertex-connected graph

Summary

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. Complete graphs are not included in this version of the definition since they cannot be disconnected by deleting vertices. The complete graph with n vertices has connectivity n − 1, as implied by the first definition.
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 . This definition produces the same answer, n − 1, for the connectivity of the complete graph Kn.
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). 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 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 .

Official source

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 units (1)

Related people (21)

Related courses (4)

Related publications (65)

Related concepts (16)

Related lectures (33)

This course is an introduction to the theory of Riemann surfaces. Riemann surfaces naturally appear is mathematics in many different ways: as a result of analytic continuation, as quotients of complex

This course introduces statistical field theory, and uses concepts related to phase transitions to discuss a variety of complex systems (random walks and polymers, disordered systems, combinatorial o

A first graduate course in algorithms, this course assumes minimal background, but moves rapidly. The objective is to learn the main techniques of algorithm analysis and design, while building a reper

Vertex separator

In graph theory, a vertex subset S \subset V is a vertex separator (or vertex cut, separating set) for nonadjacent vertices a and b if the removal of S from the graph separates a and b into distinct connected components. Consider a grid graph with r rows and c columns; the total number n of vertices is r × c. For instance, in the illustration, r = 5, c = 8, and n = 40. If r is odd, there is a single central row, and otherwise there are two rows equally close to the center; similarly, if c is odd, there is a single central column, and otherwise there are two columns equally close to the center.

Connectivity (graph theory)

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) 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 an undirected graph G, two vertices u and v are called connected if G contains a path from u to v.

Steinitz's theorem

In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs. That is, every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, the 3-connected planar graphs are also known as polyhedral graphs.

Lee-Yang Theory

Explores the Lee-Yang theory, covering connected graphs, paths, phase diagrams, and analytic continuation.

Topology of Riemann Surfaces

Covers the topology of Riemann surfaces and the concept of triangulation using finitely many triangles.

Vectorworks Educational Version

Introduces Vectorworks Educational Version for architectural drawings, covering tools, layers, and annotations.

, ,

Many image-based perception tasks can be formulated as detecting, associating and tracking semantic keypoints, e.g., human body pose estimation and tracking. In this work, we present a general framework that jointly detects and forms spatio-temporal keypoi ...

Orthogonal group synchronization is the problem of estimating n elements Z(1),& mldr;,Z(n) from the rxr orthogonal group given some relative measurements R-ij approximate to Z(i)Z(j)(-1). The least-squares formulation is nonconvex. To avoid its local minim ...

Philippe Schwaller, Junwu Chen

Graph neural networks (GNNs) have demonstrated promising performance across various chemistry-related tasks. However, conventional graphs only model the pairwise connectivity in molecules, failing to adequately represent higher order connections, such as m ...