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.

A graph with connectivity 4.

The vertex-connectivity, or just connectivity, of a graph is the largest k for which the graph is k-vertex-connected.

Definitions

edit

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.

Applications

edit

Components

edit

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.

Polyhedral combinatorics

edit

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.

Computational complexity

edit

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  .

Properties

edit

Let k≥2.

  • Every  -connected graph of order at least   contains a cycle of length at least  
  • In a  -connected graph, any   vertices in   lie on a common cycle.[5]

The cycle space of a  -connected graph is generated by its non-separating induced cycles. [6]

k-linked graph

edit

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]

See also

edit

Notes

edit
  1. ^ a b Schrijver (12 February 2003), Combinatorial Optimization, Springer, ISBN 9783540443896
  2. ^ Beineke, Lowell W.; Bagga, Jay S. (2021), Line Graphs and Line Digraphs, Developments in Mathematics, vol. 68, Springer Nature, p. 87, ISBN 9783030813864
  3. ^ Balinski, M. L. (1961), "On the graph structure of convex polyhedra in n-space", Pacific Journal of Mathematics, 11 (2): 431–434, doi:10.2140/pjm.1961.11.431.
  4. ^ The algorithm design manual, p 506, and Computational discrete mathematics: combinatorics and graph theory with Mathematica, p. 290-291
  5. ^ Diestel (2016), p.84
  6. ^ Diestel (2012), p.65.
  7. ^ Diestel (2016), p.85
  8. ^ Diestel (2016), p.75

References

edit
  • Diestel, Reinhard (2005), Graph Theory (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4
  • Diestel, Reinhard (2012), Graph Theory (corrected 4th electronic ed.)
  • Diestel, Reinhard (2016), Graph Theory (5th ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-662-53621-6