2
$\begingroup$

Given a graph $G$, let $H$ be a $k$-degenerate (not necessarily induced) subgraph of maximal size. Are there any known lower bounds on $|E(H)|$ for particular classes of $G$ and values of $k$?

I've seen several papers on the subject, but only for induced subgraphs $H$. I'm particularly interested in the case where $k=2$ and $G$ is both regular and bipartite, but any additional information would be helpful.

(I'm aware of the naive lower bound found by arbitrarily removing edges until no vertex has degree $(k+1)$ or more...I'm looking for something better).

Improve this question
$\endgroup$
2
  • $\begingroup$ what does $k$-degenerate means? $\endgroup$
    – Dima Pasechnik
    Commented Sep 24, 2012 at 7:03
  • 1
    $\begingroup$ @Dima - $k$-degenerate means that every subgraph has a vertex of degree at most $k$. Equivalently, repeatedly remove the vertex of minimum degree until the graph is gone; the degeneracy number of the graph is the biggest degree you saw along the way. $\endgroup$
    – Gordon Royle
    Commented Sep 24, 2012 at 22:47

2 Answers 2

Reset to default
1
$\begingroup$

Here are some very minor and mostly negative observations in the k=2 case. Obviously a 2-degenerate subgraph in an n-vertex graph can have at most 2n-3 edges. So let's ask which graphs have 2-degenerate subgraphs with exactly 2n-3 edges. Vertices of degree at most 2 can force the answer to be "no". So let's assume minimum degree at least 3. And if a graph has c components, then every 2-degenerate subgraph has at most 2n-3c edges. So let's assume that our graph is connected. But still there are graphs for which every 2-degenerate subgraph has strictly less than 2n-3 edges. Let G be a connected graph with 6 vertices of degree 3 and n-6 vertices of degree 4. (There are many ways to construct such a graph, starting from K_{3,3}.) So the total number of edges is 2n-3, but the graph itself is not 2-degenerate. So there is no 2-degenerate subgraph of G with 2n-3 edges.

I am interested in this question, so if you know something else, then please email [email protected]

Improve this answer
$\endgroup$
1
$\begingroup$

Just a minor remark (that might be useful, who knows?)

Any $2k$-edge-connected graph on $n$ vertices contains a spanning $(2k-1)$-degenerate subgraph on $k(n-1)$ edges.

Proof: by Nash-Williams, a $2k$-edge-connected graph contains $k$ edge-disjoint spanning trees. The spanning subgraph whose edge-set consists of the union of these $k$ spanning trees is $(2k-1)$-degenerate and contains $k(n-1)$ edges.

Improve this answer
$\endgroup$

You must log in to answer this question.

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