9
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\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

0

Reset to default

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.