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
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 18, 2017 at 15:38 | vote | accept | Ozzy | ||
| S Aug 17, 2017 at 9:58 | history | suggested | Peter Heinig | CC BY-SA 3.0 |
During my rewrite, I accidentally misstated the concept the OP is asking for in the new *title*. Corrected.
|
| Aug 17, 2017 at 9:43 | comment | added | Jon Noel | @PeterHeinig, to me, that paper doesn't seem to be relevant. I've added a link to a more relevant one in my answer. | |
| Aug 17, 2017 at 9:13 | review | Suggested edits | |||
| S Aug 17, 2017 at 9:58 | |||||
| S Aug 17, 2017 at 8:40 | history | suggested | Peter Heinig | CC BY-SA 3.0 |
I think the form of the OP was an unbearable mess, yet I think the substance of the OP is legitimate for MO. I therefore *rewrote* the OP from scratch, to what I think is usual form. This summary form is too small to document the changes. I think that the meaning of the OP was not changed at all.
|
| Aug 17, 2017 at 8:20 | comment | added | Peter Heinig | Dear @Ozzy: a published article extremely relevant to your question (though not explicitly addressing precisely what you seem to be asking for) is Daniela Kühn, Deryk Osthus: Partitions of graphs with high minimum degree or connectivity. Journal of Combinatorial Theory, Series B. Volume 88, Issue 1, May 2003, Pages 29-43 | |
| Aug 17, 2017 at 8:16 | comment | added | Peter Heinig | Dear @Ozzy: I think there were so many infelicities and malapropisms in the original formulation of the OP that a complete (meaning-preserving) rewrite of the OP was in order. If you have reasons to prefer some of your formulations, please say so, and/or roll back. Documenting all my changes would get too long: only so much: 'network' tends to be used in a specific, quite different sense nowadays, 'agents' is not usual graph theoretic language. There were logical issues too with the OP, too. | |
| Aug 17, 2017 at 8:11 | review | Suggested edits | |||
| S Aug 17, 2017 at 8:40 | |||||
| Aug 17, 2017 at 7:46 | answer | added | Jon Noel | timeline score: 5 | |
| Aug 16, 2017 at 21:03 | comment | added | Gerhard Paseman | Try the following. Set G to G_0. Given G_n, find and remove all the vertices (and corresponding edges) in G_n of lowest degree, and call what's left G_{n+1}. For many G, the progression of graphs G_n will see an increase in the graph parameter minimal degree. I think when this parameter hits k, G_n will be your S_k. You might look at degree sequences and processes of building or deconstructing graphs. Gerhard " Doesn't Know Technical Graph Terminology" Paseman, 2017.08.16. | |
| Aug 16, 2017 at 18:50 | review | First posts | |||
| Aug 16, 2017 at 18:57 | |||||
| Aug 16, 2017 at 18:46 | history | asked | Ozzy | CC BY-SA 3.0 |