2
$\begingroup$

Let $G=(V,E)$ be a simple undirected graph. Define an mmd$k$s in $G$ (for 'maximal minimum degree $k$ subset') to be any subset $S$ of $V$ such that

  1. the subgraph induced by $S$ in $G$ has minimum degree $\geq k$,
  2. $S$ is $\subseteq$-maximal w.r.t. property 1.

Moreover, for any $k$, let $\mathrm{smmds}(G,k):=\sup\{ \lvert S \rvert \colon\text{$S$ is an mmd$k$s in $G$}\}$.

Moreover, for any class $\mathbb{G}$ of graphs, let $\mathrm{smmds}(\mathbb{G},k):=\sup\{ \mathrm{smmds}(G,k)\colon G\in\mathbb{G}\}$.

My question is whether

  • mmd$k$s's
  • the graph invariant $\mathrm{smmds}(\cdot,k)$,

have already been analysed and named in graph theory.

I am interested in understanding how $\mathrm{smmds}(\cdot,k)$, varies, as a function of $k$, for different families of graphs (or certain random graph models).

Improve this question
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Gerhard Paseman
    Commented Aug 16, 2017 at 21:03
  • $\begingroup$ 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. $\endgroup$
    – Peter Heinig
    Commented Aug 17, 2017 at 8:16
  • $\begingroup$ 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 $\endgroup$
    – Peter Heinig
    Commented Aug 17, 2017 at 8:20
  • $\begingroup$ @PeterHeinig, to me, that paper doesn't seem to be relevant. I've added a link to a more relevant one in my answer. $\endgroup$
    – Jon Noel
    Commented Aug 17, 2017 at 9:43

1 Answer 1

Reset to default
5
$\begingroup$

According to Wikipedia, a $k$-core of a graph $G$ is a maximal connected subgraph $K$ of $G$ such that every vertex of $K$ has degree at least $k$. Apart from the "connected" part of the definition, this is the same as your set $S_k$. Your set $S_k$ is the union of the vertex sets of all $k$-cores of $G$.

Similar to what Gerhard suggested, you can find the set $S_k$ by initialising $S_k:=V(G)$ and then repeatedly deleting every vertex of degree less than $k$ in the subgraph induced by $S_k$ until there are no such vertices left (note that this may terminate with $S_k=\emptyset$).

With regards to $k$-cores in random graphs, one natural place to start might be the paper Size and connectivity of the $k$-core of a random graph by Tomasz Łuczak.

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – Peter Heinig
    Commented Aug 17, 2017 at 9:30
  • 1
    $\begingroup$ @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. $\endgroup$
    – Jon Noel
    Commented Aug 17, 2017 at 9:36
  • $\begingroup$ 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? $\endgroup$
    – Peter Heinig
    Commented Aug 17, 2017 at 9:52
  • $\begingroup$ 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. $\endgroup$
    – Jon Noel
    Commented Aug 17, 2017 at 9:53
  • 2
    $\begingroup$ 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. $\endgroup$
    – Gerhard Paseman
    Commented Aug 17, 2017 at 15:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .