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

image 1

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?

image 2

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.

  • $\begingroup$ What is the source you quoted that definition from? $\endgroup$ – bof Nov 27 '18 at 11:21
  • $\begingroup$ I got the definition from the 3rd page in the pdf article named "Best monotone degree conditions for binding number and cycle structure". $\endgroup$ – Buddhini Angelika Nov 27 '18 at 13:47
  • $\begingroup$ Don't you want to give credit to the author of that article? Can you provide a link? $\endgroup$ – bof Nov 27 '18 at 13:53
  • $\begingroup$ 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. $\endgroup$ – Buddhini Angelika Nov 27 '18 at 16:45
  • $\begingroup$ Can some one please help me to understand this. $\endgroup$ – 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\}$.

  • $\begingroup$ Thank you very much @mathnoob $\endgroup$ – Buddhini Angelika Nov 28 '18 at 16:15
  • $\begingroup$ 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 $\endgroup$ – Buddhini Angelika Nov 28 '18 at 16:18
  • $\begingroup$ DId you aske the author about this? $\endgroup$ – mathpadawan Nov 28 '18 at 16:44

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.