Inductively defined sequence of graph neighborhoods
$begingroup$
I'm trying to solve the following problem:
Let $v_0$ be a vertex in a graph $G$, and $D_0 := {v_0}$.
For $n = 1, 2 dots$ inductively define
$D_n := N(D_0 cup D_1 cup dots cup D_{n-1})$.
Show that $D_n = {v | d(v_0, v) = n}$ and
$D_{n+1} subseteq N(D_n) subseteq D_{n-1} cup D_{n+1}$ for all
$n in mathbb{N}$.
Here, $N_G(V') = N(V')$ is the neighborhood of $V' subseteq V(G)$, and
$d_G(u, v) = d(u, v)$ is the distance in $G$ of two vertices $u$, $v$.
I'm unable to solve the task because I am not sure if it's correctly defined. Every type of graph seems to be a contradiction to the statements above. Consider for simplicity the following example:
Let $P$ be a path, and $v_0$ be the central vertex in $P$. Then
$D_0 = {v_0}$,
$D_1 = N(D_0) = {v | d(v_0, v) = 1}$,
$D_2 = N(D_0 cup D_1) = N({v_0} cup N({v_0})) =
{v | d(v_0, v) leq 2}$,
and for all $n geq 2$ we obtain $D_n = {v | d(v_0, v) leq n}$. In particular, it follows that $V(P) = D_r$, where $r$ is the radius of $P$.
This example contradicts both statements in the second part of the task. Can you, please, help me find out, is there anything I am missing or interpreting incorrectly?
graph-theory
asked Feb 6 at 8:16
Sanjar AdylovSanjar Adylov
284
$endgroup$
add a comment |
$begingroup$
I'm trying to solve the following problem:
Let $v_0$ be a vertex in a graph $G$, and $D_0 := {v_0}$.
For $n = 1, 2 dots$ inductively define
$D_n := N(D_0 cup D_1 cup dots cup D_{n-1})$.
Show that $D_n = {v | d(v_0, v) = n}$ and
$D_{n+1} subseteq N(D_n) subseteq D_{n-1} cup D_{n+1}$ for all
$n in mathbb{N}$.
Here, $N_G(V') = N(V')$ is the neighborhood of $V' subseteq V(G)$, and
$d_G(u, v) = d(u, v)$ is the distance in $G$ of two vertices $u$, $v$.
I'm unable to solve the task because I am not sure if it's correctly defined. Every type of graph seems to be a contradiction to the statements above. Consider for simplicity the following example:
Let $P$ be a path, and $v_0$ be the central vertex in $P$. Then
$D_0 = {v_0}$,
$D_1 = N(D_0) = {v | d(v_0, v) = 1}$,
$D_2 = N(D_0 cup D_1) = N({v_0} cup N({v_0})) =
{v | d(v_0, v) leq 2}$,
and for all $n geq 2$ we obtain $D_n = {v | d(v_0, v) leq n}$. In particular, it follows that $V(P) = D_r$, where $r$ is the radius of $P$.
This example contradicts both statements in the second part of the task. Can you, please, help me find out, is there anything I am missing or interpreting incorrectly?
graph-theory
asked Feb 6 at 8:16
Sanjar AdylovSanjar Adylov
284
$endgroup$
add a comment |
$begingroup$
I'm trying to solve the following problem:
Let $v_0$ be a vertex in a graph $G$, and $D_0 := {v_0}$.
For $n = 1, 2 dots$ inductively define
$D_n := N(D_0 cup D_1 cup dots cup D_{n-1})$.
Show that $D_n = {v | d(v_0, v) = n}$ and
$D_{n+1} subseteq N(D_n) subseteq D_{n-1} cup D_{n+1}$ for all
$n in mathbb{N}$.
Here, $N_G(V') = N(V')$ is the neighborhood of $V' subseteq V(G)$, and
$d_G(u, v) = d(u, v)$ is the distance in $G$ of two vertices $u$, $v$.
I'm unable to solve the task because I am not sure if it's correctly defined. Every type of graph seems to be a contradiction to the statements above. Consider for simplicity the following example:
Let $P$ be a path, and $v_0$ be the central vertex in $P$. Then
$D_0 = {v_0}$,
$D_1 = N(D_0) = {v | d(v_0, v) = 1}$,
$D_2 = N(D_0 cup D_1) = N({v_0} cup N({v_0})) =
{v | d(v_0, v) leq 2}$,
and for all $n geq 2$ we obtain $D_n = {v | d(v_0, v) leq n}$. In particular, it follows that $V(P) = D_r$, where $r$ is the radius of $P$.
This example contradicts both statements in the second part of the task. Can you, please, help me find out, is there anything I am missing or interpreting incorrectly?
graph-theory
asked Feb 6 at 8:16
Sanjar AdylovSanjar Adylov
284
$endgroup$
I'm trying to solve the following problem:
Let $v_0$ be a vertex in a graph $G$, and $D_0 := {v_0}$.
For $n = 1, 2 dots$ inductively define
$D_n := N(D_0 cup D_1 cup dots cup D_{n-1})$.
Show that $D_n = {v | d(v_0, v) = n}$ and
$D_{n+1} subseteq N(D_n) subseteq D_{n-1} cup D_{n+1}$ for all
$n in mathbb{N}$.
Here, $N_G(V') = N(V')$ is the neighborhood of $V' subseteq V(G)$, and
$d_G(u, v) = d(u, v)$ is the distance in $G$ of two vertices $u$, $v$.
I'm unable to solve the task because I am not sure if it's correctly defined. Every type of graph seems to be a contradiction to the statements above. Consider for simplicity the following example:
Let $P$ be a path, and $v_0$ be the central vertex in $P$. Then
$D_0 = {v_0}$,
$D_1 = N(D_0) = {v | d(v_0, v) = 1}$,
$D_2 = N(D_0 cup D_1) = N({v_0} cup N({v_0})) =
{v | d(v_0, v) leq 2}$,
and for all $n geq 2$ we obtain $D_n = {v | d(v_0, v) leq n}$. In particular, it follows that $V(P) = D_r$, where $r$ is the radius of $P$.
This example contradicts both statements in the second part of the task. Can you, please, help me find out, is there anything I am missing or interpreting incorrectly?
graph-theory
graph-theory
asked Feb 6 at 8:16
Sanjar AdylovSanjar Adylov
284
asked Feb 6 at 8:16
Sanjar AdylovSanjar Adylov
284
asked Feb 6 at 8:16
Sanjar AdylovSanjar Adylov
284
asked Feb 6 at 8:16
Sanjar AdylovSanjar Adylov
284
asked Feb 6 at 8:16
Sanjar AdylovSanjar Adylov
284
284
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
You are mixing closed and open neighbourhood. I think when they are stating $D_n=N(D_0cupldotscup D_{n-1})$, they are implying the open neighbourhood
The open neighbourhood $N(S)$ of some set of vertices $S$ does not include $S$. Therefore, using your exampla of the path $P$:
$D_0={v_0}$
$D_1=N(D_0)={v mid d(v_0,v)=1}$
$D_2=N(D_0cup D_1)={v mid d(v_0,v)=2}$
and so on.
More precisely if you define $P$ as:
$$ ldots v_{-n} ldots v_{-2} v_1 v_0 v_1 v_2 ldots v_n ldots$$
Then $D_0={v_0}$, $D_1=N(D_0)={v_1,v_{-1}}$, and
$$D_2=N(D_0cup D_1)= N({v_1,v_0,v_{-1}})={v_2,v_{-2}}$$
Therefore the statements holds as
begin{align*}
D_{n+1}={v_{n+1},v_{-(n+1)}} &subset N(D_n)=N({v_{n},v_{-n}})={v_{n+1},v_{n-1},v_{-(n-1)},v_{-(n+1)}}\
&subset D_{n-1} cup D_{n+1}
end{align*}
with an equality in your specific case of $P$
answered Feb 6 at 9:16
Thomas LesgourguesThomas Lesgourgues
1,285220
$endgroup$
1
$begingroup$
Yes, this. I've seen people use the notation $N(X)$ for open neighbourhood and $N[X]$ for closed neighbourhood.
$endgroup$
– Especially Lime
Feb 6 at 9:17
$begingroup$
Indeed $N(X)$ can mean a few different things, after all this time I am not really sure which is the standard. $N(X)$ could be $S_1 doteq {v: vx in E$ for some $x in X}$... $N(X)$ could mean $S_1 cup X$ or it could mean $S_1 setminus X$.
$endgroup$
– Mike
Feb 6 at 21:10
add a comment |
$begingroup$
It depends on how you define the neighbourhood, but it seems that here it is defined so that $N(V')$ comprises the vertices adjacent to some vertex in $V'$, excluding vertices in $V'$.
So in that case, $N(D_0cup D_1)neq {v|d(v_0,v)leq 2}$.
answered Feb 6 at 9:15
broncoAbiertobroncoAbierto
28819
$endgroup$
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3102210%2finductively-defined-sequence-of-graph-neighborhoods%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
You are mixing closed and open neighbourhood. I think when they are stating $D_n=N(D_0cupldotscup D_{n-1})$, they are implying the open neighbourhood
The open neighbourhood $N(S)$ of some set of vertices $S$ does not include $S$. Therefore, using your exampla of the path $P$:
$D_0={v_0}$
$D_1=N(D_0)={v mid d(v_0,v)=1}$
$D_2=N(D_0cup D_1)={v mid d(v_0,v)=2}$
and so on.
More precisely if you define $P$ as:
$$ ldots v_{-n} ldots v_{-2} v_1 v_0 v_1 v_2 ldots v_n ldots$$
Then $D_0={v_0}$, $D_1=N(D_0)={v_1,v_{-1}}$, and
$$D_2=N(D_0cup D_1)= N({v_1,v_0,v_{-1}})={v_2,v_{-2}}$$
Therefore the statements holds as
begin{align*}
D_{n+1}={v_{n+1},v_{-(n+1)}} &subset N(D_n)=N({v_{n},v_{-n}})={v_{n+1},v_{n-1},v_{-(n-1)},v_{-(n+1)}}\
&subset D_{n-1} cup D_{n+1}
end{align*}
with an equality in your specific case of $P$
answered Feb 6 at 9:16
Thomas LesgourguesThomas Lesgourgues
1,285220
$endgroup$
1
$begingroup$
Yes, this. I've seen people use the notation $N(X)$ for open neighbourhood and $N[X]$ for closed neighbourhood.
$endgroup$
– Especially Lime
Feb 6 at 9:17
$begingroup$
Indeed $N(X)$ can mean a few different things, after all this time I am not really sure which is the standard. $N(X)$ could be $S_1 doteq {v: vx in E$ for some $x in X}$... $N(X)$ could mean $S_1 cup X$ or it could mean $S_1 setminus X$.
$endgroup$
– Mike
Feb 6 at 21:10
add a comment |
$begingroup$
You are mixing closed and open neighbourhood. I think when they are stating $D_n=N(D_0cupldotscup D_{n-1})$, they are implying the open neighbourhood
The open neighbourhood $N(S)$ of some set of vertices $S$ does not include $S$. Therefore, using your exampla of the path $P$:
$D_0={v_0}$
$D_1=N(D_0)={v mid d(v_0,v)=1}$
$D_2=N(D_0cup D_1)={v mid d(v_0,v)=2}$
and so on.
More precisely if you define $P$ as:
$$ ldots v_{-n} ldots v_{-2} v_1 v_0 v_1 v_2 ldots v_n ldots$$
Then $D_0={v_0}$, $D_1=N(D_0)={v_1,v_{-1}}$, and
$$D_2=N(D_0cup D_1)= N({v_1,v_0,v_{-1}})={v_2,v_{-2}}$$
Therefore the statements holds as
begin{align*}
D_{n+1}={v_{n+1},v_{-(n+1)}} &subset N(D_n)=N({v_{n},v_{-n}})={v_{n+1},v_{n-1},v_{-(n-1)},v_{-(n+1)}}\
&subset D_{n-1} cup D_{n+1}
end{align*}
with an equality in your specific case of $P$
answered Feb 6 at 9:16
Thomas LesgourguesThomas Lesgourgues
1,285220
$endgroup$
1
$begingroup$
Yes, this. I've seen people use the notation $N(X)$ for open neighbourhood and $N[X]$ for closed neighbourhood.
$endgroup$
– Especially Lime
Feb 6 at 9:17
$begingroup$
Indeed $N(X)$ can mean a few different things, after all this time I am not really sure which is the standard. $N(X)$ could be $S_1 doteq {v: vx in E$ for some $x in X}$... $N(X)$ could mean $S_1 cup X$ or it could mean $S_1 setminus X$.
$endgroup$
– Mike
Feb 6 at 21:10
add a comment |
$begingroup$
You are mixing closed and open neighbourhood. I think when they are stating $D_n=N(D_0cupldotscup D_{n-1})$, they are implying the open neighbourhood
The open neighbourhood $N(S)$ of some set of vertices $S$ does not include $S$. Therefore, using your exampla of the path $P$:
$D_0={v_0}$
$D_1=N(D_0)={v mid d(v_0,v)=1}$
$D_2=N(D_0cup D_1)={v mid d(v_0,v)=2}$
and so on.
More precisely if you define $P$ as:
$$ ldots v_{-n} ldots v_{-2} v_1 v_0 v_1 v_2 ldots v_n ldots$$
Then $D_0={v_0}$, $D_1=N(D_0)={v_1,v_{-1}}$, and
$$D_2=N(D_0cup D_1)= N({v_1,v_0,v_{-1}})={v_2,v_{-2}}$$
Therefore the statements holds as
begin{align*}
D_{n+1}={v_{n+1},v_{-(n+1)}} &subset N(D_n)=N({v_{n},v_{-n}})={v_{n+1},v_{n-1},v_{-(n-1)},v_{-(n+1)}}\
&subset D_{n-1} cup D_{n+1}
end{align*}
with an equality in your specific case of $P$
answered Feb 6 at 9:16
Thomas LesgourguesThomas Lesgourgues
1,285220
$endgroup$
You are mixing closed and open neighbourhood. I think when they are stating $D_n=N(D_0cupldotscup D_{n-1})$, they are implying the open neighbourhood
The open neighbourhood $N(S)$ of some set of vertices $S$ does not include $S$. Therefore, using your exampla of the path $P$:
$D_0={v_0}$
$D_1=N(D_0)={v mid d(v_0,v)=1}$
$D_2=N(D_0cup D_1)={v mid d(v_0,v)=2}$
and so on.
More precisely if you define $P$ as:
$$ ldots v_{-n} ldots v_{-2} v_1 v_0 v_1 v_2 ldots v_n ldots$$
Then $D_0={v_0}$, $D_1=N(D_0)={v_1,v_{-1}}$, and
$$D_2=N(D_0cup D_1)= N({v_1,v_0,v_{-1}})={v_2,v_{-2}}$$
Therefore the statements holds as
begin{align*}
D_{n+1}={v_{n+1},v_{-(n+1)}} &subset N(D_n)=N({v_{n},v_{-n}})={v_{n+1},v_{n-1},v_{-(n-1)},v_{-(n+1)}}\
&subset D_{n-1} cup D_{n+1}
end{align*}
with an equality in your specific case of $P$
answered Feb 6 at 9:16
Thomas LesgourguesThomas Lesgourgues
1,285220
answered Feb 6 at 9:16
Thomas LesgourguesThomas Lesgourgues
1,285220
answered Feb 6 at 9:16
Thomas LesgourguesThomas Lesgourgues
1,285220
answered Feb 6 at 9:16
Thomas LesgourguesThomas Lesgourgues
1,285220
1,285220
1
$begingroup$
Yes, this. I've seen people use the notation $N(X)$ for open neighbourhood and $N[X]$ for closed neighbourhood.
$endgroup$
– Especially Lime
Feb 6 at 9:17
$begingroup$
Indeed $N(X)$ can mean a few different things, after all this time I am not really sure which is the standard. $N(X)$ could be $S_1 doteq {v: vx in E$ for some $x in X}$... $N(X)$ could mean $S_1 cup X$ or it could mean $S_1 setminus X$.
$endgroup$
– Mike
Feb 6 at 21:10
add a comment |
1
$begingroup$
Yes, this. I've seen people use the notation $N(X)$ for open neighbourhood and $N[X]$ for closed neighbourhood.
$endgroup$
– Especially Lime
Feb 6 at 9:17
$begingroup$
Indeed $N(X)$ can mean a few different things, after all this time I am not really sure which is the standard. $N(X)$ could be $S_1 doteq {v: vx in E$ for some $x in X}$... $N(X)$ could mean $S_1 cup X$ or it could mean $S_1 setminus X$.
$endgroup$
– Mike
Feb 6 at 21:10
1
1
$begingroup$
Yes, this. I've seen people use the notation $N(X)$ for open neighbourhood and $N[X]$ for closed neighbourhood.
$endgroup$
– Especially Lime
Feb 6 at 9:17
$begingroup$
Yes, this. I've seen people use the notation $N(X)$ for open neighbourhood and $N[X]$ for closed neighbourhood.
$endgroup$
– Especially Lime
Feb 6 at 9:17
$begingroup$
Indeed $N(X)$ can mean a few different things, after all this time I am not really sure which is the standard. $N(X)$ could be $S_1 doteq {v: vx in E$ for some $x in X}$... $N(X)$ could mean $S_1 cup X$ or it could mean $S_1 setminus X$.
$endgroup$
– Mike
Feb 6 at 21:10
$begingroup$
Indeed $N(X)$ can mean a few different things, after all this time I am not really sure which is the standard. $N(X)$ could be $S_1 doteq {v: vx in E$ for some $x in X}$... $N(X)$ could mean $S_1 cup X$ or it could mean $S_1 setminus X$.
$endgroup$
– Mike
Feb 6 at 21:10
add a comment |
$begingroup$
It depends on how you define the neighbourhood, but it seems that here it is defined so that $N(V')$ comprises the vertices adjacent to some vertex in $V'$, excluding vertices in $V'$.
So in that case, $N(D_0cup D_1)neq {v|d(v_0,v)leq 2}$.
answered Feb 6 at 9:15
broncoAbiertobroncoAbierto
28819
$endgroup$
add a comment |
$begingroup$
It depends on how you define the neighbourhood, but it seems that here it is defined so that $N(V')$ comprises the vertices adjacent to some vertex in $V'$, excluding vertices in $V'$.
So in that case, $N(D_0cup D_1)neq {v|d(v_0,v)leq 2}$.
answered Feb 6 at 9:15
broncoAbiertobroncoAbierto
28819
$endgroup$
add a comment |
$begingroup$
It depends on how you define the neighbourhood, but it seems that here it is defined so that $N(V')$ comprises the vertices adjacent to some vertex in $V'$, excluding vertices in $V'$.
So in that case, $N(D_0cup D_1)neq {v|d(v_0,v)leq 2}$.
answered Feb 6 at 9:15
broncoAbiertobroncoAbierto
28819
$endgroup$
It depends on how you define the neighbourhood, but it seems that here it is defined so that $N(V')$ comprises the vertices adjacent to some vertex in $V'$, excluding vertices in $V'$.
So in that case, $N(D_0cup D_1)neq {v|d(v_0,v)leq 2}$.
answered Feb 6 at 9:15
broncoAbiertobroncoAbierto
28819
answered Feb 6 at 9:15
broncoAbiertobroncoAbierto
28819
answered Feb 6 at 9:15
broncoAbiertobroncoAbierto
28819
answered Feb 6 at 9:15
broncoAbiertobroncoAbierto
28819
28819
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3102210%2finductively-defined-sequence-of-graph-neighborhoods%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
