PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (191)
Orphanage
Unclass'd (1)
Unproven (496)
Corrections (5)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very low Entry average rating: No information on entry rating
${k}$-connected graph (Definition)

Connectivity of graphs, when it isn't specified which flavor is intended, usually refers to vertex connectivity, unless it is clear from the context that it refers to edge connectivity.

The (vertex) connectivity $\kappa(G)$ is the minimum number of vertices (aka nodes) you have to remove to either make the graph no longer connected, or reduce it to a single vertex (node). $G$ is said to be $k$-(vertex)-connected for any $k\le\kappa(G)\in{\mathchoice {{\sf I\kern-.12emN}}{{\sf I\kern-.12emN}}{{\S\sf I\kern-.12emN}}{{\SS\sf I\kern-.12emN}}}$. Note that “removing a vertex” in graph theory also involves removing all the edges incident to that vertex.

The edge connectivity $\kappa'(G)$ of a graph $G$ is more straightforward, it is just the minimum number of edges you have to remove to make the graph no longer connected. $G$ is said to be $k$-edge-connected for any $k\le\kappa'(G)\in{\mathchoice {{\sf I\kern-.12emN}}{{\sf I\kern-.12emN}}{{\S\sf I\kern-.12emN}}{{\SS\sf I\kern-.12emN}}}$. And note “removing an edge” is simply that; it does not entail removing any vertices.

  • If $\kappa'(G)=0$ also $\kappa(G)=0$ and vice versa; such graphs are called disconnected and consist of several connected components. If $\kappa$ and $\kappa'$ are nonzero (the graph is 1-connected) it is a connected graph (a single connected component)
  • If $\kappa'(G)=1$ the graph contains at least one bridge. If $\kappa'(G)\gt1$ (the graph is 2-edge-connected) every edge is part of a cycle (circuit, closed path).

    If $\kappa(G)=1$ the graph contains at least one cutvertex. If $\kappa(G)\gt1$ (the graph is 2-vertex-connected) there is, for any pair of vertices, a cycle they both lie on.

  • For the complete graphs we have $\kappa(K_n)=\kappa'(K_n)=n-1$.
  • For any graph $G$ we have $\kappa(G) \le \kappa'(G) \le \delta(G)$ where the latter is the minimum valency in $G$ (the valency of a vertex is the number of edges sprouting from it).

Everything on this page applies equally well to multigraphs and pseudographs.

For directed graphs there are two notions of connectivity (“weak” if the underlying graph is connected, “strong” if you can get from everywhere to everywhere).

There are now pictures to go with this entry.



"${k}$-connected graph" is owned by marijke. [ full author list (2) | owner history (1) ]
(view preamble)

View style:

See Also: connected graph, (closed) walk / trek / trail / path

Also defines:  ${k}$-connected ${k}$-vertex-connected ${k}$-edge-connected connectivity

Attachments:
examples of ${k}$-connected graphs (Example) by marijke
Log in to rate this entry.
(view current ratings)

Cross-references: directed graphs, pseudographs, multigraphs, valency, complete graphs, lie on, cutvertex, closed path, circuit, cycle, bridge, contains, connected components, disconnected, incident, graph theory, connected, number, edge, clear, vertex, graphs
There are 3 references to this entry.

This is version 4 of ${k}$-connected graph, born on 2002-11-29, modified 2005-04-05.
Object id is 3630, canonical name is KConnectedGraph.
Accessed 4385 times total.

Classification:
AMS MSC: 05C40 (Combinatorics :: Graph theory :: Connectivity)
Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)