Talk:Connectivity (graph theory)
| WikiProject Mathematics (Rated Start-Class) | |||
|---|---|---|---|
 |
|||
| Mathematics rating: | Start Class | Mid Priority | Field: Discrete mathematics |
|
Please update this rating as the article progresses, or if the rating is inaccurate. |
|||
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 |
[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 
, there is either a path from 
to 
or a path from to ? 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)
- Please define the maximal in maximal connected subgraph. Thanks, --Abdull (talk) 15:27, 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 K1 to be connected. I think that means its connectivity is 1, not 0. Agreed? McKay (talk) 07:43, 8 March 2009 (UTC)
[edit] Menger's theorem
The article's statement of Menger's theorem (the final paragraph of the Menger's theorem section) appears to me to be trivially false, and different from the statement given at Menger's theorem. Maproom (talk) 16:32, 5 November 2010 (UTC)
