Talk:Dense subgraph

[Untitled]

should subgraph density be defined similarly to graph density? graph density is |E| / choose(|V|, 2), yet subgraph density here is defined as |E| / |V|.

Mmuurr (talk) 20:10, 12 July 2013 (UTC)

First sentence confusing?

The first sentence of the article currently reads: "In graph theory and computer science, a dense subgraph is a subgraph with a high level of internal connectivity."

But the notion of connectivity here confused me when first reading it.

Consider the following example of a 4-regular graph on 10 vertices that contains a 2-edge cut:

Let $ax$ and $by$ be the edges of the 2-edge cut. Insert 3 parallel edges between $a$ and $b$, subdivide them introducing vertices $c,d,e$, and connect these new vertices by a triangle $cde$. Similarly on the $x,y$ side.

Now, being 4-regular, it has a subgraph density of 2, and any proper subgraph has a lower density. But if we wanted to maximise internal connectivity, we would have chosen one of the "sides", e.g. $a,b,c,d,e$, which I believe is 3-edge connected.

Vuniu (talk) 08:21, Dec 31, 2022 (ECT) — Preceding undated comment added 07:31, 31 December 2022 (UTC)

"Connectivity" here was intended in a less formal sense than the one you are using. But your suggested replacement, "average degree", would also be confusing. For instance, in a Star (graph theory), the central vertex has high degree, and so the subgraph consisting only of that vertex would seem to have high average degree (if you measure degree in terms of the whole graph, not the subgraph). But it is not a dense subgraph. One possibility would be to replace "a high level of internal connectivity" with "many edges per vertex", or something like that. —David Eppstein (talk) 07:58, 31 December 2022 (UTC)

I absolutely see, now, why my suggested replacement was also confusing.

The suggestion of "many edges per vertex" (or something like that) sounds much better. Vuniu (talk) 14:49, 31 December 2022 (UTC)

Example incorrect

The example does not show the densest subgraph ... the induced graph $G'=(V' = \{b,c,d,e,f,g,h\}, \choose{V'}{2} \cap E(G))$ has density $d_{G'} = \frac{10}{7} = 1.428571 > 1.4 = \frac{7}{5}$ — Preceding unsigned comment added by 134.34.225.175 (talk) 13:07, 12 August 2014 (UTC)