Talk:Connectivity (graph theory)

This is the talk page for discussing improvements to the Connectivity (graph theory) article.
This is not a forum for general discussion of the article's subject.

Put new text under old text. Click here to start a new topic.
New to Wikipedia? Welcome! Learn to edit; get help.

Article policies

Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL

Untitled

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]
  - 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)[reply]

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)[reply]

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)[reply]

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Connectivity (graph theory). Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

Added archive https://web.archive.org/web/20100611212234/http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps to http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 06:10, 12 August 2017 (UTC)[reply]

Proposed merge of Meshulam game into Connectivity (graph theory)

The following discussion is closed. Please do not modify it. Subsequent comments should be made in a new section. A summary of the conclusions reached follows.

To not merge, given opposition and no support; no consensus for any other particular action. Klbrain (talk) 11:35, 13 February 2021 (UTC)[reply]

The new article Meshulam game concerns a theorem about the connectivity of a graph, in particular, a bound relating the connectivity to the outcome of a certain game on the graph. I am skeptical that the game is sufficiently notable to merit a full article. However, it is short and could fit nicely as a section in this article. What do others think? JBL (talk) 20:32, 31 July 2020 (UTC)[reply]

As far as I understand from the references, this game is about the standard notion of graph connectivity - it is about the homological connectivity of a graph. It may be better to merge it to that page. I am still working on these issues. --Erel Segal (talk) 20:04, 1 August 2020 (UTC)[reply]

Better not. The "game" is a separate well defined (sub)subject. My very best wishes (talk) 18:41, 12 December 2020 (UTC)[reply]

The discussion above is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.