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

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.

edited Nov 27 '18 at 16:44

asked Nov 27 '18 at 10:37

Buddhini Angelika

15710

$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

add a comment |

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

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

Thanks a lot in advance.

edited Nov 27 '18 at 16:44

asked Nov 27 '18 at 10:37

Buddhini Angelika

15710

$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

add a comment |

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

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

Thanks a lot in advance.

edited Nov 27 '18 at 16:44

asked Nov 27 '18 at 10:37

Buddhini Angelika

15710

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

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

Thanks a lot in advance.

abstract-algebra graph-theory finite-groups cayley-graphs

edited Nov 27 '18 at 16:44

asked Nov 27 '18 at 10:37

Buddhini Angelika

15710

edited Nov 27 '18 at 16:44

asked Nov 27 '18 at 10:37

Buddhini Angelika

15710

edited Nov 27 '18 at 16:44

asked Nov 27 '18 at 10:37

Buddhini Angelika

15710

asked Nov 27 '18 at 10:37

Buddhini Angelika

15710

asked Nov 27 '18 at 10:37

Buddhini Angelika

15710

$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

add a comment |

$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

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

add a comment |

1 Answer
1

active

oldest

votes

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

answered Nov 28 '18 at 6:46

nafhgood

1,797422

$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$
– nafhgood
Nov 28 '18 at 16:44

add a comment |

Your Answer

StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\$","\$"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});

}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3015621%2fa-question-related-to-the-binding-number-of-a-graph%23new-answer', 'question_page');
}
);