0
$\begingroup$

(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$?

Improve this question
$\endgroup$
4
  • $\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
    Commented Feb 21, 2016 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
    Commented Feb 21, 2016 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
    Commented Feb 21, 2016 at 4:10
  • $\begingroup$ @BrendanMcKay Could you post a full-fledged solution? $\endgroup$
    – user76479
    Commented Feb 21, 2016 at 4:11

1 Answer 1

Reset to default
3
$\begingroup$

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.

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

You must log in to answer this question.