A question related to the binding number of a graph

Question

I came across with a definition for the "binding number" of a graph as below. $G$ is a graph and $V(G)$ is the vertex set of graph $G$.

There it is mentioned as "min". Does that mean the minimum possible case because there can be vertices where the neighbourhood may overlap with each other? Which elements should be chosen for the set S?

Note: $N(S)$ is the open neighbourhood and a vertex of $S$ might or might not be in $N(S)$.

Can some one please guide me to find the binding number of the Petersen graph?

Which vertices should be chosen to the set S out of the vertices labelled as in the above figure and how to take the elements of $N(S)$?

The link to the article I'm referring is: https://ac.els-cdn.com/S0012365X11001981/1-s2.0-S0012365X11001981-main.pdf?_tid=c520ed95-dcda-4ff0-9514-e6d2d0c5d317&acdnat=1543336951_1d736cd5f428e19ddaaf90a714bd825d

Thanks a lot in advance.

Answer 1

Let's consider singleton vertex set first.

Let $S=\{1\}$, then $N(S)=\{5,6,2\}$, so $\frac{|N(S)|}{|S|}=3$.

Let $S=\{1,2\}$, $N(S)=\{5,6,7,3,1,2\}$, so $\frac{|N(S)|}{|S|}=\frac{6}{2}=3$.

let $S=\{1,3\}$, $N(S)=\{5,6,2,8,9 \}$ So $\frac{|N(S)|}{|S|}=\frac{5}{2}$.

Suppose $S=\{1,2,3\}$, then $N(S)=\{1,2,3,4,5,6,7,8\}$, so $\frac{|N(S)|}{|S|}=\frac{8}{3}$.

Suppose $S=\{1,10,3\}$, then $N(S)=\{5,6,2,7,8,4\}$ so $\frac{|N(S)|}{|S|}=\frac{6}{3}=3$.

Let $S=\{1,6,10\}$, then $N(S)=\{5,2,8,9,1,7\}$, so $\frac{|N(S)|}{|S|}=\frac{6}{3}=3$

Let $S=\{1,2,6,7,8\}$,then $N(S)=\{5,6,2,1,7,3,9,8,10\}$ so $\frac{|N(S)|}{|S|}=\frac{9}{5}$.

Let $S=\{1,2,6,7,8,10\}$, then $N(S)=\{5,6,2,1,7,3,9,8,10\}$ so $\frac{|N(S)|}{|S|}=\frac{9}{6}=\frac{3}{2}$.

So I bet, the answer is $\frac{3}{2}$ and $S$ could be $\{1,2,6,7,8,10\}$.

Answer 2

Take any vertex $v$. Let $S$ be the non-neighbors of $v$ (including $v$ itself). Then $S$ has $7$ vertices and $N(S)$ has $9$ vertices. Hence the binding number of the Petersen graph is at most $\frac{9}{7}$.