# A question related to the binding number of a graph

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

• What is the source you quoted that definition from? – bof Nov 27 '18 at 11:21
• I got the definition from the 3rd page in the pdf article named "Best monotone degree conditions for binding number and cycle structure". – Buddhini Angelika Nov 27 '18 at 13:47
• Don't you want to give credit to the author of that article? Can you provide a link? – bof Nov 27 '18 at 13:53
• Sorry. I have edited the question including the link now. It is present under the proof of Theorem 1.3. Thanks a lot in advance. – Buddhini Angelika Nov 27 '18 at 16:45
• Can some one please help me to understand this. – Buddhini Angelika Nov 28 '18 at 4:19

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\}$$.

• Thank you very much @mathnoob – Buddhini Angelika Nov 28 '18 at 16:15
• But in that article in theorem 1.4 it is mentioned that if the binding number is greater than or equal to $3/2$ it is hamiltonian, but the petersen graph is not Hamiltonian. Please help me to clarify this idea – Buddhini Angelika Nov 28 '18 at 16:18