Talk:Connectivity (graph theory)

From Wikipedia, the free encyclopedia

WikiProject Mathematics     (Rated Start-Class)
Mathematics portal This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating:	Start Class	Mid Priority	Field: Discrete mathematics
Please update this rating as the article progresses, or if the rating is inaccurate. Click to show/hide comments. Please add to or update the comments to suggest improvements to the article. Longer lead and references would help. Geometry guy 22:41, 16 June 2007 (UTC)

Could somebody kindly provide information on different categories of connectivity, such as 'weakly connected graph', 'strongly connected graph' etc..?

As I understand it, these two terms refer to directed graphs; I've added the definitions I know.JLeander 23:47, 2 February 2006 (UTC)

Contents 1 Figures 2 Fulkerson's theorem 3 Question about digraphs 4 Maximal 5 complete graphs

[edit] Figures

It would be nice to have some figures in here, wouldn't it? Maybe I will cook some up at some point using xfig.JLeander 23:47, 2 February 2006 (UTC)

[edit] Fulkerson's theorem

An earlier version of the page had a reference to "Fulkerson's theorem." My MathSciNet search didn't turn up any appropriate result known by this name. My guess is that the previous editor had max-flow/min-cut in mind---or am I missing something?JLeander 23:47, 2 February 2006 (UTC)

[edit] Question about digraphs

What's the name for a digraph such that for each pair of vertices u,v, there is either a path from u to v or a path from v to u? I'd call it just connected, since this is an intermediate property between weak and strong connectivity, and is in fact equivalent to the existence of a path containing all vertices. However, I'm not an expert of the subject, and I was unable to find any reference about this, so far. fudo (questions?) 17:35, 27 April 2007 (UTC)

[edit] Maximal

• A connected component is a maximal connected subgraph of G.
  • Please define the maximal in maximal connected subgraph. Thanks, --Abdull (talk) 15:27, 27 July 2008 (UTC)
    • See Maximal element. In this context it means, a connected subgraph that is not part of any larger connected subgraph. —David Eppstein (talk) 17:25, 27 July 2008 (UTC)

[edit] complete graphs

"A complete graph with n vertices has no cuts at all, but by convention its connectivity is n-1." Agreed, except that everyone considers K₁ to be connected. I think that means its connectivity is 1, not 0. Agreed? McKay (talk) 07:43, 8 March 2009 (UTC)