K-edge-connected graph

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 fewer than k edges from the graph.

If a graph G is k-edge-connected then k le delta(G), where delta(G) is the minimum degree of any vertex v in V(G). This fact is clear since deleting all edges with an end at a vertex of minimum degree will disconnect that vertex from the graph.

See also

* k-vertex-connected graph
* Connectivity (graph theory)
* Menger's theorem


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • 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 …   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

  • Edge coloring — A 3 edge coloring of the Desargues graph. In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge… …   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

  • Edge-graceful labeling — In graph theory, an edge graceful graph labeling is a type of graph labeling. This is a labeling for simple graphs , namely ones in which no two distinct edges connect the same two distinct vertices, no edge connects a vertex to itself, and the… …   Wikipedia

  • 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

  • Nauru graph — The Nauru graph is Hamiltonian. Vertices 24 Edges 36 Radius 4 …   Wikipedia

  • Edge contraction — In graph theory, an edge contraction is an operation which removes an edge from a graph while simultaneously merging together the two vertices it previously connected. Edge contraction is a fundamental operation in the theory of graph minors.… …   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

  • Holt graph — In the Holt graph, all vertices are equivalent, and all edges are equivalent, but edges are not necessarily equivalent to their inverses. Named after Derek F. Holt Vertices 27 …   Wikipedia

Share the article and excerpts

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