(1.) How small can set $S$ of vertices in any regular undirected graph $G$ on $n$ vertices with degree $\Omega(n^\alpha)$ where $\alpha\in(0,1)$ can be such that every edge in the graph is incident on at least one vertex in $S$? For instance is $|S|\leq\frac nc$ always possible with some fixed $c>1$ (say $c=2$)?

(2.) Moreover consider the subgraph $G_S$ with vertex set $S$ and edge set consisting of edges in $G$ with both end points in $S$. Can we pick an $S$ such that subgraph $G_S$ is regular? What is the least degree that $G_S$ can have?

So in essence what is the product of least degree and minimal cardinality possible for $G_S$?

  • $\begingroup$ No. Consider if $G$ has a perfect matching (eg if it is bipartite). At least one end of each edge of the matching must be in $S$, so $|S|\ge n/2$. $\endgroup$ – Brendan McKay Feb 21 '16 at 2:47
  • $\begingroup$ @BrendanMcKay From your argument it seems like if we have $k$-partite graph we should have $|S|\leq\frac nc$ with $c\geq{1-\frac1k}$. $\endgroup$ – user76479 Feb 21 '16 at 3:06
  • $\begingroup$ More generally, the complement of $S$ is an independent set and the converse holds too. So finding a minimum $S$ is the same problem as finding a maximum independent set. Note that an $r$-regular non-complete graph has an independent set of size at least $n/r$. $\endgroup$ – Brendan McKay Feb 21 '16 at 4:10
  • $\begingroup$ @BrendanMcKay Could you post a full-fledged solution? $\endgroup$ – user76479 Feb 21 '16 at 4:11

The complement of $S$ is an independent set, so the minimum value of $|S|$ is $n-\alpha(G)$ where $\alpha(G)$ is the size of the largest independent set. For non-complete connected regular graphs of degree $r$, there is an independent set of size $n/r$ since the chromatic number is at most $r$. So you can find $S$ with $|S|\le n(1-1/r)$. For complete graphs obviously $|S|=n-1$ is the best you can do.

  • $\begingroup$ Estimate $n\cdot r/(r+1)$ works also for not connected graphs, and is sharp $\endgroup$ – Fedor Petrov Feb 21 '16 at 9:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy