K-vertex-connected graph

K-vertex-connected graph

In graph theory, a graph "G" with vertex set "V(G)" is said to be "k"-vertex-connected (or "k"-connected) if G setminus X is connected for all X subseteq V(G) with left| X ight| < k. In plain English, a graph is "k"-connected if the graph remains connected when you delete fewer than "k" vertices from the graph. Or, equivalently (owing to Menger's theorem), a graph is "k"-connected if any two of its vertices can be joined by "k" independent paths Harv|Diestel|2005| p=55.

A 1-vertex-connected graph is connected, while a 2-vertex-connected graph is said to be biconnected.

If a graph "G" is "k"-vertex-connected, and "k" < |"V(G)"|, then k le delta(G), where "δ(G)" is the minimum degree of any vertex v in V(G). This fact is clear since deleting all neighbors of a vertex of minimum degree will disconnect that vertex from the rest of the graph.

The 1-skeleton of any "k"-dimensional convex polytope forms a k-vertex-connected graph (Balinski 1961). As a partial converse, Steinitz showed that any 3-vertex-connected planar graph forms the skeleton of a convex polyhedron.

References

*cite journal
author = Balinski, M. L.
title = On the graph structure of convex polyhedra in "n"-space
journal = Pacific Journal of Mathematics
volume = 11
issue = 2
year = 1961
pages = 431–434
url = http://www.projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.pjm/1103037323

*.

See also

* k-edge-connected graph
* Connectivity (graph theory)
* Menger's theorem
* Structural cohesion


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • K-edge-connected graph — In graph theory, a graph G with edge set E(G) is said to be k edge connected if G setminus X is connected for all X subseteq E(G) with left| X ight| < k. In plain English, a graph is k edge connected if the graph remains connected when you delete …   Wikipedia

  • Graph (mathematics) — This article is about sets of vertices connected by edges. For graphs of mathematical functions, see Graph of a function. For statistical graphs, see Chart. Further information: Graph theory A drawing of a labeled graph on 6 vertices and 7 edges …   Wikipedia

  • Vertex (graph theory) — For other uses, see Vertex (disambiguation). A graph with 6 vertices and 7 edges where the vertex number 6 on the far left is a leaf vertex or a pendant vertex In graph theory, a vertex (plural vertices) or node is the fundamental unit out of… …   Wikipedia

  • Graph toughness — In graph theory, toughness is a measure of the connectivity of a graph. A graph G is said to be t tough if, for every k > 1, G cannot be split into k different connected components by the removal of fewer than tk vertices. For instance, a graph… …   Wikipedia

  • graph theory — Math. the branch of mathematics dealing with linear graphs. [1965 70] * * * Mathematical theory of networks. A graph consists of nodes (also called points or vertices) and edges (lines) connecting certain pairs of nodes. An edge that connects a… …   Universalium

  • Graph of groups — In geometric group theory, a graph of groups is an object consisting of a collection of groups indexed by the vertices and edges of a graph, together with a family of injective homomorphisms of the edge groups into the vertex groups.There is a… …   Wikipedia

  • 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) which need to be removed to disconnect the remaining nodes from each other[1]. It is… …   Wikipedia

  • Degeneracy (graph theory) — In graph theory, a k degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph s edges. The degeneracy of a graph is the smallest… …   Wikipedia

  • Coxeter graph — This article is about the 3 regular graph. For the graph associated with a Coxeter group, see Coxeter diagram. Coxeter graph The Coxeter graph Vertices 28 Edges 42 …   Wikipedia

  • Biconnected graph — In the mathematical discipline of graph theory, a biconnected graph is a connected graph with no articulation vertices.In other words, a biconnected graph is nonseparable, meaning if any vertex were to be removed, the graph will remain… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”