Timeline for Subsets of a graph, maximal w.r.t. the property of inducing a subgraph with minimum degree at least $k$
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 18, 2017 at 15:38 | vote | accept | Ozzy | ||
| Aug 18, 2017 at 0:13 | comment | added | Ozzy | Dear @JonNoel. It turns out that k-cores are exactly what I was looking for. Thanks for the pointers! | |
| Aug 17, 2017 at 17:55 | history | edited | Jon Noel | CC BY-SA 3.0 |
added 145 characters in body
|
| Aug 17, 2017 at 15:43 | comment | added | Gerhard Paseman | To make things more explicit, write the k-core of G as K, and note that every vertex in K has degree at least k (in K as well as in G). The current reading allows one to take K out of context, and allow vertices of K to have had degree k in G, not necessarily degree k in K. Gerhard "Cake Or K Core Or..." Paseman, 2017.08.17. | |
| Aug 17, 2017 at 10:00 | history | edited | Jon Noel | CC BY-SA 3.0 |
added 2 characters in body
|
| Aug 17, 2017 at 10:00 | comment | added | Peter Heinig | Dear @Jon Noel: thanks for the answer. Re your question: the reason is simply, as I now realized, I have heretofore worked with an apparently less usual definition of 'core', which has 'degree'='degree within the ambient graph'. For several reasons (among them: I understand that one should not excessively chat here), I will now go offline and leave you to clarify whatever you think there is to clarify. Thanks for the discussion. | |
| Aug 17, 2017 at 9:59 | history | edited | Jon Noel | CC BY-SA 3.0 |
added 2 characters in body
|
| Aug 17, 2017 at 9:53 | comment | added | Jon Noel | Why do you think that $\{1,2\}$ is a $2$-core in that graph (which I assume is a path on $4$ vertices)? By the way, I've realised that the $k$-core is actually clearly unique (the disconnected thing doesn't actually matter). I've edited my answer to reflect this. | |
| Aug 17, 2017 at 9:52 | history | edited | Jon Noel | CC BY-SA 3.0 |
added 11 characters in body
|
| Aug 17, 2017 at 9:52 | comment | added | Peter Heinig | Dear @Jon Noel, thanks, yes, you are right that one should delete the offending vertices outright (and I was misled by something which still does not seem right in the current version of your answer: you write "$S_k$ is the union of the vertex sets of the $k$-cores of the graph". This seems false for $0\text{--}1\text{--}2\text{--}3$ which has $\{1,2\}$ as its $2$-core, yet, as you correctly point out, has $S_k=\emptyset$, so here $S_k$ is not the union of the cores. (Btw, you should tell the OP that the only reason for non-unique cores are non-connected $G$.) Would you please clarify? | |
| Aug 17, 2017 at 9:51 | history | edited | Jon Noel | CC BY-SA 3.0 |
added 253 characters in body
|
| Aug 17, 2017 at 9:45 | history | edited | Jon Noel | CC BY-SA 3.0 |
added 253 characters in body
|
| Aug 17, 2017 at 9:36 | comment | added | Jon Noel | @PeterHeinig, I disagree. He is not simply asking to find the set of vertices of degree at least $k$ in a graph (which would be completely trivial...), he wants a maximal set that induces a subgraph of minimum degree $k$. Therefore, it is not a bad thing that deleting vertices lowers the degree of other vertices; you simply must delete those vertices to obtain such a set. By the way, it is possible that this algorithm outputs the empty set, but this makes sense; $S_k$ might actually be empty. | |
| Aug 17, 2017 at 9:30 | comment | added | Peter Heinig | Dear @Jon Noel: this is correct. One small thing: I would not write "delete", but rather leave out every vertex of degree less than $k$, here (even though e.g. the Wikipedia article you link to do), since 'delete' seems to me to carry misleading connotations: one must not delete offending vertices (which would in general lower the degree of the vertices one is aiming to be left with), rather leaves them by the wayside. If in your (correct) algorithm, you really deleted the offenders from the data structure, you are losing so much information that you will not in general find the core. | |
| Aug 17, 2017 at 8:07 | history | edited | Jon Noel | CC BY-SA 3.0 |
added 137 characters in body
|
| Aug 17, 2017 at 7:46 | history | answered | Jon Noel | CC BY-SA 3.0 |