Jump to content

Talk:K-edge-connected graph

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

This should NOT redirect from "k-connected graph". The two are very distinct concepts, and the latter NEEDS an entry...

You're right. Fixed. —David Eppstein 16:49, 22 October 2006 (UTC)[reply]

This seems to be redundant, given the Connectivity (graph theory) article. Radagast3 (talk) 00:18, 1 May 2008 (UTC)[reply]

There is plenty of material to expand this and K-vertex-connected graph into two separate long articles. —David Eppstein (talk) 00:20, 1 May 2008 (UTC)[reply]
Agreed, but I'm too busy to do it. ;) Radagast3 (talk) 00:36, 1 May 2008 (UTC)[reply]

Complexity

[edit]

Gabow's paper states complexity, not . Reminiscenza (talk) 11:40, 2 June 2015 (UTC)[reply]

There's no contradiction between those two bounds. k is necessarily O(n) and m is necessarily O(n2). So if you eliminate those two variables and express everything in terms of n, you get O(n3).—David Eppstein (talk) 15:20, 2 June 2015 (UTC)[reply]
Yes, but why we need to express everything in terms of n? For graph algorithms, complexity is usually expressed in terms of m and n, and whatever other parameters available - so that the bound is useful for both sparse and dense graphs. Bound is at least misleading for sparse graphs, where it is possible that , and overall complexity would be , much better than . — Preceding unsigned comment added by Reminiscenza (talkcontribs) 06:21, 3 June 2015 (UTC)[reply]

Proper math

[edit]
  • In graph theory, a graph with edge set is said to be -edge-connected if is connected for all with .
    • Is it syntactically correct to say , as G is a graph (= a set of vertices and a set of edges connecting some vertices) whereas X is a set of edges? --Abdull (talk) 15:33, 27 July 2008 (UTC)[reply]

Stronger

[edit]
  • If a graph is -edge-connected then , where is the minimum degree of any vertex .
    • Can we make this theorem stronger by saying , as we could delete all but one edges from a vertex and still have all vertices of this connected graph connected? --Abdull (talk) 15:55, 27 July 2008 (UTC)[reply]

Consistency

[edit]

It is usual, even on this WIKI, to write a graph as an ordered pair (V,E) with vertex set V and edge set E. This article does it the other way around. Is there a compelling reason for this? Leen Droogendijk (talk) 11:31, 28 June 2012 (UTC)[reply]

Contradiction between the formal definition and the next section

[edit]

Consider a graph G of a single vertex and no edge. According to the formal definition, G is k-edge-connected for all k. On the other hand, the minimum vertex degree of G is 0, thus the statement of the second section does not hold for this example. --Jalpar75 —Preceding undated comment added 15:59, 9 August 2013 (UTC)[reply]