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 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 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 (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 greater than $k$. This subcase is already challenging because it is open 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?

  • $\begingroup$ 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)\}$). $\endgroup$
    – GMB
    Aug 9, 2018 at 21:50
  • $\begingroup$ 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. $\endgroup$
    – Yixin Cao
    Aug 19, 2018 at 7:33
  • $\begingroup$ @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. $\endgroup$
    – a3nm
    Aug 19, 2018 at 19:35


Your Answer

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