4
$\begingroup$

The $k$-core of a finite graph is defined as follows. Delete all vertices of degree $< k$ and repeat until there are no such vertices left. If there is a nonempty subgraph remaining, necessarily of minimum degree $\ge k$, we call this graph the $k$-core. If the deletion process results in removing all vertices, we say that the graph has no $k$-core.

Let $f(n,k)$ denote the maximum number of edges in a simple graph on $n$ vertices with no $k$-core. For example, if $f(n,2)=n-1$ for every $n$, since $n$ edges are sufficient (and necessary) to guarantee the existence of a cycle.

What about $k \ge 3$? Maybe a formula is too much to hope for, so for fixed $k$ what are the asymptotics of $f(n,k)$ as $n \to \infty$?

I suspect this kind of question has been studied, so any references would be appreciated. It is very similar in flavor to questions in "classical" extremal graph theory, where one tries to maximize the number of edges in a graph on $n$ vertices with no $H$-subgraph, where $H$ is a fixed graph. This question fits in a more general setting where $H$ ranges over an infinite family of possible subgraphs.

$\endgroup$
1
  • $\begingroup$ I think you want "of minimum degree >= k". Also, the literature on triangle free graphs may hint at an answer for f(n,3), even though it will only give an upper bound, and possibly a very weak bound. If you specialize to bipartite graphs, (I am guessing) you might also find some literature. Gerhard "Ask Me About System Design" Paseman, 2013.03.01 $\endgroup$ Mar 1, 2013 at 17:17

2 Answers 2

8
$\begingroup$

$$f(n,k)= (n-k)(k-1)+\frac{k(k-1)}{2}, \; \mathrm{for} \; n \geq k, $$ $$f(n,k) = \frac{n(n-1)}{2}, \; \mathrm{for} \; n \leq k. $$

Proof: Every graph with no $k$-core on $n$ vertices contains a vertex of degree $\leq k-1$ which one can delete, obtaining a graph with no $k$-core. Thus $$f(n,k) \leq f(n-1,k) + k-1.$$

The formula now follows by induction. In the base case $n \leq k$ the formula gives the number of edges in the complete graph.

For an example that the bound can be achieved, let $G$ be a graph with $V(G) = \{1,2, \ldots, n \}$ and let the vertices $i$ and $j$ be adjacent if and only if $|i-j| < k$. It is easy to check that $G$ has no $k$-core and has the right number of edges.

$\endgroup$
3
$\begingroup$

If I'm not confused, I believe the graphs you are searching for (with a $k-1$ core but no $k$-core, and adding any edge creates a $k$-core) are also called "maximal $(k-1)$-degenerate graphs," see e.g. the wikipedia article on degeneracy.

The paper "k-degenerate graphs" of Lick and White proves the following:

Corollary 1: Let $G$ be a maximal $k$-degenerate graph with $p$ points, $p\geq k$. Then $G$ has $kp-\binom{k+1}{2}$ [edges].

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.