Return to Question

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

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?

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

Is there a set $S$ of $O(n^{1-\alpha})$ vertices in any regular undirected graph $G$ on $n$ vertices with degree $\Omega(n^\alpha)$ where $\alpha\in(0,1)$ such that every edge in the graph is incident on at least one vertex in $S$?

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?

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

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?

Is there a set $S$ of $O(n^{1-\alpha})$ vertices in any regular undirected graph $G$ on $n$ vertices with degree $\Omega(n^\alpha)$ where $\alpha\in(0,1)$ such that every edge in the graph is incident on at least one vertex in $S$?

Is there a set $S$ of $O(n^{1-\alpha})$ vertices in any regular undirected graph $G$ on $n$ vertices with degree $\Omega(n^\alpha)$ where $\alpha\in(0,1)$ such that every edge in the graph is incident on at least one vertex in $S$?

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?