<p>I consider undirected graphs $G = (V, E)$ for which I write $\text{n}(G) := |V|$ the number of vertices and $\text{m}(G) := |E|$ the number of edges. For $d \in \mathbb{N}$, I say that $G$ is <a href="https://en.wikipedia.org/wiki/Regular_graph" rel="noreferrer">$d$-regular</a> if every vertex of $G$ occurs in exactly $d$ edges. For $W \subseteq V$ a subset of vertices of $G$, I write $G|_W$ the <a href="https://en.wikipedia.org/wiki/Induced_subgraph" rel="noreferrer">induced subgraph</a> of $G$ by $W$: its vertex set is $W$ and its edge set is the restriction of $E$ to $W$, i.e., the edges of $G$ whose endpoints are both in $W$.</p>

<p>Given a graph $G$, I am interested in the function $f_G$ from $\{0, \ldots, \text{n}(G)\}$ to $\mathbb{N}$ defined by:</p>

<p>$$f_G(k) := \max_{W \subseteq V \text{ such that } |W| = k} \text{m}(G|_W).$$</p>

<p>Informally, $f_G(k)$ is the maximal number of edges in an induced subgraph of $k$ vertices of $G$. Of course, it is NP-hard to compute $f_G$ given $G$, because of a straightforward reduction from the <a href="https://en.wikipedia.org/wiki/Clique_problem" rel="noreferrer">clique problem</a> (we have $f_G(k) = {k \choose 2}$ if and only if $G$ contains a $k$-clique), but I'm just interested in the function, not in computing it. <strong>Does this function have a name, or does it relate to known concepts in graph theory?</strong> In particular I'm interested in regular graphs where this function grows as slowly as possible: specifically let's define the following for any $n, d \in \mathbb{N}$ and $0 \leq k \leq n$:</p>

<p>$$g(n, k, d) := \min_{G~d\text{-regular such that } \text{n}(G) = n} f_G(k)$$</p>

<p>Informally, this is the lowest value of $f_G(k)$ for a $d$-regular graph with $n$ vertices and $m$ edges. <strong>Is anything known about the behavior of this function $g$?</strong></p>

<p>One specific angle under which $g$ seems to have been studied is that of finding the values for which $g(n, k, d) = k-1$ (i.e., the lowest value we can reasonably hope for): this holds iff there exists a $d$-regular graph on $n$ vertices with <a href="https://en.wikipedia.org/wiki/Girth_(graph_theory)" rel="noreferrer">girth</a> greater than $k$. This subcase is already challenging because <a href="https://en.wikipedia.org/wiki/Cage_(graph_theory)#Asymptotics" rel="noreferrer">it is open</a> to determine exactly for which values such a graph exists; but the asymptotics are known. I wonder if anything is known more generally about the function $g$, e.g., when fixing $d$, if $k$ is some $\Omega(\log n)$, then we may have $g(n, k, d) &gt; k-1$, but can we still bound the value of $g$ somehow?</p>

CC BY-SA 4.0
2018-08-09T21:50:44.450Z
Small point about your high-girth graphs: the asymptotics are only kind of known.  The densest $d$-regular graph with girth $> k$ has $d = n^{\Theta(1/k)}$.  So the extremal value of $d$ is only known up to polynomials, not constant factors (except, it turns out, it's known up to constant factors in the special cases $k \in \{3, 4, 5, 6, 7, 10, 11, \Omega(\log n)\}$).
GMB
CC BY-SA 4.0
2018-08-19T07:33:13.860Z
It's not necessary to emphasize "induced" subgraphs in the problem formulation. Since you are looking for a subgraph with the maximum number of edges, it's implicitly induced.
Yixin Cao
CC BY-SA 4.0
2018-08-19T19:35:23.547Z
@YixinCao: That's right, thanks for pointing it out. I was defining the problem in terms of induced subgraphs because the number of vertices of the subgraph is what matters so I thought this was easier, but indeed the problem doesn't change if $f_G$ is defined by taking the max over all subgraphs with at most $k$ vertices.
Antoine Amarilli 'a3nm'
<reference-request><graph-theory><extremal-combinatorics>
Graphs with minimal-size induced subgraphs
Antoine Amarilli 'a3nm'
# Graphs with minimal-size induced subgraphs

(Asked by: username_0 on 2018-08-09)

I consider undirected graphs $G = (V, E)$ for which I write $\text{n}(G) := |V|$ the number of vertices and $\text{m}(G) := |E|$ the number of edges. For $d \in \mathbb{N}$, I say that $G$ is [$d$-regular](https://en.wikipedia.org/wiki/Regular_graph) if every vertex of $G$ occurs in exactly $d$ edges. For $W \subseteq V$ a subset of vertices of $G$, I write $G|\_W$ the [induced subgraph](https://en.wikipedia.org/wiki/Induced_subgraph) of $G$ by $W$: its vertex set is $W$ and its edge set is the restriction of $E$ to $W$, i.e., the edges of $G$ whose endpoints are both in $W$.

Given a graph $G$, I am interested in the function $f\_G$ from $\{0, \ldots, \text{n}(G)\}$ to $\mathbb{N}$ defined by:

$$f\_G(k) := \max\_{W \subseteq V \text{ such that } |W| = k} \text{m}(G|\_W).$$

Informally, $f\_G(k)$ is the maximal number of edges in an induced subgraph of $k$ vertices of $G$. Of course, it is NP-hard to compute $f\_G$ given $G$, because of a straightforward reduction from the [clique problem](https://en.wikipedia.org/wiki/Clique_problem) (we have $f\_G(k) = {k \choose 2}$ if and only if $G$ contains a $k$-clique), but I'm just interested in the function, not in computing it. **Does this function have a name, or does it relate to known concepts in graph theory?** In particular I'm interested in regular graphs where this function grows as slowly as possible: specifically let's define the following for any $n, d \in \mathbb{N}$ and $0 \leq k \leq n$:

$$g(n, k, d) := \min\_{G~d\text{-regular such that } \text{n}(G) = n} f\_G(k)$$

Informally, this is the lowest value of $f\_G(k)$ for a $d$-regular graph with $n$ vertices and $m$ edges. **Is anything known about the behavior of this function $g$?**

One specific angle under which $g$ seems to have been studied is that of finding the values for which $g(n, k, d) = k-1$ (i.e., the lowest value we can reasonably hope for): this holds iff there exists a $d$-regular graph on $n$ vertices with [girth](https://en.wikipedia.org/wiki/Girth_(graph_theory)) greater than $k$. This subcase is already challenging because [it is open](https://en.wikipedia.org/wiki/Cage_(graph_theory)#Asymptotics) to determine exactly for which values such a graph exists; but the asymptotics are known. I wonder if anything is known more generally about the function $g$, e.g., when fixing $d$, if $k$ is some $\Omega(\log n)$, then we may have $g(n, k, d) > k-1$, but can we still bound the value of $g$ somehow?

**Tags:** reference-request, graph-theory, extremal-combinatorics
> **Comments:**
> **username_1**: Small point about your high-girth graphs: the asymptotics are only kind of known.  The densest $d$-regular graph with girth $> k$ has $d = n^{\Theta(1/k)}$.  So the extremal value of $d$ is only known up to polynomials, not constant factors (except, it turns out, it's known up to constant factors in the special cases $k \in \{3, 4, 5, 6, 7, 10, 11, \Omega(\log n)\}$).  
> **username_2**: It's not necessary to emphasize "induced" subgraphs in the problem formulation. Since you are looking for a subgraph with the maximum number of edges, it's implicitly induced.  
> **username_0**: @YixinCao: That's right, thanks for pointing it out. I was defining the problem in terms of induced subgraphs because the number of vertices of the subgraph is what matters so I thought this was easier, but indeed the problem doesn't change if $f_G$ is defined by taking the max over all subgraphs with at most $k$ vertices.  

---

## 0 answers

