Disjoint paths between four vertices The 2019 Stack Overflow Developer Survey Results Are InDisjoint Rooted Paths with Specified Patternsedges minus verticesCut Locus in a GraphCould this be a NP complete?Bounds on number of simple paths in graphProbability of two vertices being connected in a random graphConnection between connectivity and cohesion of a graphFind paths in a graph that any 2 vertices can be reached through N of themFind all edges not covered by a shortest path in an all-pairs shortest path over a subset of verticesFind a minimum set of paths that cover all pairs of dependent vertices
Disjoint paths between four vertices
The 2019 Stack Overflow Developer Survey Results Are InDisjoint Rooted Paths with Specified Patternsedges minus verticesCut Locus in a GraphCould this be a NP complete?Bounds on number of simple paths in graphProbability of two vertices being connected in a random graphConnection between connectivity and cohesion of a graphFind paths in a graph that any 2 vertices can be reached through N of themFind all edges not covered by a shortest path in an all-pairs shortest path over a subset of verticesFind a minimum set of paths that cover all pairs of dependent vertices
$begingroup$
Consider the following property of an undirected graph: For any four distinct vertices $a,b,c,d$, there is a path from $a$ to $b$ and a path from $c$ to $d$ such that the two paths do not share any vertex.
Is there a name for this property, or has it been studied? It looks related to vertex connectivity but not quite the same. Also it seems that any graph satisfying this property must have vertex connectivity at least $2$.
reference-request graph-theory
asked Apr 5 at 7:31
user137930user137930
503
New contributor
user137930 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
Consider the following property of an undirected graph: For any four distinct vertices $a,b,c,d$, there is a path from $a$ to $b$ and a path from $c$ to $d$ such that the two paths do not share any vertex.
Is there a name for this property, or has it been studied? It looks related to vertex connectivity but not quite the same. Also it seems that any graph satisfying this property must have vertex connectivity at least $2$.
reference-request graph-theory
asked Apr 5 at 7:31
user137930user137930
503
New contributor
user137930 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
1
$begingroup$
Wouldn't the vertex connectivity have to be at least $3$? If the graph $G$ can be disconnected by removing two vertices $a,b$, and if $c,d$ are in different components of $G-a-b$
$endgroup$
– bof
Apr 5 at 9:43
add a comment |
$begingroup$
Consider the following property of an undirected graph: For any four distinct vertices $a,b,c,d$, there is a path from $a$ to $b$ and a path from $c$ to $d$ such that the two paths do not share any vertex.
Is there a name for this property, or has it been studied? It looks related to vertex connectivity but not quite the same. Also it seems that any graph satisfying this property must have vertex connectivity at least $2$.
reference-request graph-theory
asked Apr 5 at 7:31
user137930user137930
503
New contributor
user137930 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
Consider the following property of an undirected graph: For any four distinct vertices $a,b,c,d$, there is a path from $a$ to $b$ and a path from $c$ to $d$ such that the two paths do not share any vertex.
Is there a name for this property, or has it been studied? It looks related to vertex connectivity but not quite the same. Also it seems that any graph satisfying this property must have vertex connectivity at least $2$.
reference-request graph-theory
reference-request graph-theory
asked Apr 5 at 7:31
user137930user137930
503
New contributor
user137930 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Apr 5 at 7:31
user137930user137930
503
New contributor
user137930 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Apr 5 at 7:31
user137930user137930
503
New contributor
user137930 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Apr 5 at 7:31
user137930user137930
503
asked Apr 5 at 7:31
user137930user137930
503
503
New contributor
user137930 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
user137930 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
user137930 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
1
$begingroup$
Wouldn't the vertex connectivity have to be at least $3$? If the graph $G$ can be disconnected by removing two vertices $a,b$, and if $c,d$ are in different components of $G-a-b$
$endgroup$
– bof
Apr 5 at 9:43
add a comment |
1
$begingroup$
Wouldn't the vertex connectivity have to be at least $3$? If the graph $G$ can be disconnected by removing two vertices $a,b$, and if $c,d$ are in different components of $G-a-b$
$endgroup$
– bof
Apr 5 at 9:43
1
1
$begingroup$
Wouldn't the vertex connectivity have to be at least $3$? If the graph $G$ can be disconnected by removing two vertices $a,b$, and if $c,d$ are in different components of $G-a-b$
$endgroup$
– bof
Apr 5 at 9:43
$begingroup$
Wouldn't the vertex connectivity have to be at least $3$? If the graph $G$ can be disconnected by removing two vertices $a,b$, and if $c,d$ are in different components of $G-a-b$
$endgroup$
– bof
Apr 5 at 9:43
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The property that you are describing is called $2$-linked. More generally, we say that a graph is $k$-linked if it has at least $2k$ vertices and for all distinct vertices $s_1, dots s_k, t_1, dots, t_k$ there are $k$-vertex disjoint paths connecting $s_i$ to $t_i$ for all $i in [k]$. Note that every $k$-linked graph is $k$-connected. The converse is not true. For example, a cycle is $2$-connected but is not $2$-linked.
However, it is a classic theorem that there is a function $f(k)$ such that every $f(k)$-connected graph is $k$-linked. The current best bound for $f(k)$ is due to Thomas and Wollan, where they prove that every $10k$-connected graph is $k$-linked. The paper is titled An improved linear edge bound for graph linkages, and is available for free on Robin Thomas' webpage.
answered Apr 5 at 9:54
Tony HuynhTony Huynh
19.6k671130
$endgroup$
$begingroup$
Thanks! Is there a better known bound for $f(k)$ than $20$ in the case $k=2$? It doesn't seem to be in the paper.
$endgroup$
– user137930
Apr 5 at 11:06
$begingroup$
Yes, $7$-connected implies $2$-linked. Actually $7$-connected implies that for every set of $4$ vertices $a,b,c,d$ there is a cycle containing $a,b,c,d$ (in that order). This is stronger than $2$-linked. See arxiv.org/abs/1808.05124
$endgroup$
– Tony Huynh
Apr 5 at 11:11
$begingroup$
Thanks again. One more question: Is it known that $6$-connected does not imply $2$-linked? The paper mentions that $7$ is tight for the cycle property, but since the path property is weaker this is unclear.
$endgroup$
– user137930
Apr 5 at 11:32
$begingroup$
Actually, the definition I used for $k$-linked is equivalent to the version where $s_1, dots, s_k, t_1, dots, t_k$ are not necessarily distinct, but the paths are required to be internally-disjoint. With this definition, $k$-linked implies $k$-ordered. So, $6$-connected does not imply $2$-linked.
$endgroup$
– Tony Huynh
Apr 5 at 11:59
$begingroup$
It's obvious that your new definition (where vertices are not necessarily distinct) implies the original one, but why are the two equivalent?
$endgroup$
– user137930
Apr 5 at 12:36
|
show 3 more comments
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: "504"
;
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
);
);
user137930 is a new contributor. Be nice, and check out our Code of Conduct.
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%2fmathoverflow.net%2fquestions%2f327207%2fdisjoint-paths-between-four-vertices%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The property that you are describing is called $2$-linked. More generally, we say that a graph is $k$-linked if it has at least $2k$ vertices and for all distinct vertices $s_1, dots s_k, t_1, dots, t_k$ there are $k$-vertex disjoint paths connecting $s_i$ to $t_i$ for all $i in [k]$. Note that every $k$-linked graph is $k$-connected. The converse is not true. For example, a cycle is $2$-connected but is not $2$-linked.
However, it is a classic theorem that there is a function $f(k)$ such that every $f(k)$-connected graph is $k$-linked. The current best bound for $f(k)$ is due to Thomas and Wollan, where they prove that every $10k$-connected graph is $k$-linked. The paper is titled An improved linear edge bound for graph linkages, and is available for free on Robin Thomas' webpage.
answered Apr 5 at 9:54
Tony HuynhTony Huynh
19.6k671130
$endgroup$
$begingroup$
Thanks! Is there a better known bound for $f(k)$ than $20$ in the case $k=2$? It doesn't seem to be in the paper.
$endgroup$
– user137930
Apr 5 at 11:06
$begingroup$
Yes, $7$-connected implies $2$-linked. Actually $7$-connected implies that for every set of $4$ vertices $a,b,c,d$ there is a cycle containing $a,b,c,d$ (in that order). This is stronger than $2$-linked. See arxiv.org/abs/1808.05124
$endgroup$
– Tony Huynh
Apr 5 at 11:11
$begingroup$
Thanks again. One more question: Is it known that $6$-connected does not imply $2$-linked? The paper mentions that $7$ is tight for the cycle property, but since the path property is weaker this is unclear.
$endgroup$
– user137930
Apr 5 at 11:32
$begingroup$
Actually, the definition I used for $k$-linked is equivalent to the version where $s_1, dots, s_k, t_1, dots, t_k$ are not necessarily distinct, but the paths are required to be internally-disjoint. With this definition, $k$-linked implies $k$-ordered. So, $6$-connected does not imply $2$-linked.
$endgroup$
– Tony Huynh
Apr 5 at 11:59
$begingroup$
It's obvious that your new definition (where vertices are not necessarily distinct) implies the original one, but why are the two equivalent?
$endgroup$
– user137930
Apr 5 at 12:36
|
show 3 more comments
$begingroup$
The property that you are describing is called $2$-linked. More generally, we say that a graph is $k$-linked if it has at least $2k$ vertices and for all distinct vertices $s_1, dots s_k, t_1, dots, t_k$ there are $k$-vertex disjoint paths connecting $s_i$ to $t_i$ for all $i in [k]$. Note that every $k$-linked graph is $k$-connected. The converse is not true. For example, a cycle is $2$-connected but is not $2$-linked.
However, it is a classic theorem that there is a function $f(k)$ such that every $f(k)$-connected graph is $k$-linked. The current best bound for $f(k)$ is due to Thomas and Wollan, where they prove that every $10k$-connected graph is $k$-linked. The paper is titled An improved linear edge bound for graph linkages, and is available for free on Robin Thomas' webpage.
answered Apr 5 at 9:54
Tony HuynhTony Huynh
19.6k671130
$endgroup$
$begingroup$
Thanks! Is there a better known bound for $f(k)$ than $20$ in the case $k=2$? It doesn't seem to be in the paper.
$endgroup$
– user137930
Apr 5 at 11:06
$begingroup$
Yes, $7$-connected implies $2$-linked. Actually $7$-connected implies that for every set of $4$ vertices $a,b,c,d$ there is a cycle containing $a,b,c,d$ (in that order). This is stronger than $2$-linked. See arxiv.org/abs/1808.05124
$endgroup$
– Tony Huynh
Apr 5 at 11:11
$begingroup$
Thanks again. One more question: Is it known that $6$-connected does not imply $2$-linked? The paper mentions that $7$ is tight for the cycle property, but since the path property is weaker this is unclear.
$endgroup$
– user137930
Apr 5 at 11:32
$begingroup$
Actually, the definition I used for $k$-linked is equivalent to the version where $s_1, dots, s_k, t_1, dots, t_k$ are not necessarily distinct, but the paths are required to be internally-disjoint. With this definition, $k$-linked implies $k$-ordered. So, $6$-connected does not imply $2$-linked.
$endgroup$
– Tony Huynh
Apr 5 at 11:59
$begingroup$
It's obvious that your new definition (where vertices are not necessarily distinct) implies the original one, but why are the two equivalent?
$endgroup$
– user137930
Apr 5 at 12:36
|
show 3 more comments
$begingroup$
The property that you are describing is called $2$-linked. More generally, we say that a graph is $k$-linked if it has at least $2k$ vertices and for all distinct vertices $s_1, dots s_k, t_1, dots, t_k$ there are $k$-vertex disjoint paths connecting $s_i$ to $t_i$ for all $i in [k]$. Note that every $k$-linked graph is $k$-connected. The converse is not true. For example, a cycle is $2$-connected but is not $2$-linked.
However, it is a classic theorem that there is a function $f(k)$ such that every $f(k)$-connected graph is $k$-linked. The current best bound for $f(k)$ is due to Thomas and Wollan, where they prove that every $10k$-connected graph is $k$-linked. The paper is titled An improved linear edge bound for graph linkages, and is available for free on Robin Thomas' webpage.
answered Apr 5 at 9:54
Tony HuynhTony Huynh
19.6k671130
$endgroup$
The property that you are describing is called $2$-linked. More generally, we say that a graph is $k$-linked if it has at least $2k$ vertices and for all distinct vertices $s_1, dots s_k, t_1, dots, t_k$ there are $k$-vertex disjoint paths connecting $s_i$ to $t_i$ for all $i in [k]$. Note that every $k$-linked graph is $k$-connected. The converse is not true. For example, a cycle is $2$-connected but is not $2$-linked.
However, it is a classic theorem that there is a function $f(k)$ such that every $f(k)$-connected graph is $k$-linked. The current best bound for $f(k)$ is due to Thomas and Wollan, where they prove that every $10k$-connected graph is $k$-linked. The paper is titled An improved linear edge bound for graph linkages, and is available for free on Robin Thomas' webpage.
answered Apr 5 at 9:54
Tony HuynhTony Huynh
19.6k671130
edited Apr 5 at 10:27
answered Apr 5 at 9:54
Tony HuynhTony Huynh
19.6k671130
answered Apr 5 at 9:54
Tony HuynhTony Huynh
19.6k671130
answered Apr 5 at 9:54
Tony HuynhTony Huynh
19.6k671130
19.6k671130
$begingroup$
Thanks! Is there a better known bound for $f(k)$ than $20$ in the case $k=2$? It doesn't seem to be in the paper.
$endgroup$
– user137930
Apr 5 at 11:06
$begingroup$
Yes, $7$-connected implies $2$-linked. Actually $7$-connected implies that for every set of $4$ vertices $a,b,c,d$ there is a cycle containing $a,b,c,d$ (in that order). This is stronger than $2$-linked. See arxiv.org/abs/1808.05124
$endgroup$
– Tony Huynh
Apr 5 at 11:11
$begingroup$
Thanks again. One more question: Is it known that $6$-connected does not imply $2$-linked? The paper mentions that $7$ is tight for the cycle property, but since the path property is weaker this is unclear.
$endgroup$
– user137930
Apr 5 at 11:32
$begingroup$
Actually, the definition I used for $k$-linked is equivalent to the version where $s_1, dots, s_k, t_1, dots, t_k$ are not necessarily distinct, but the paths are required to be internally-disjoint. With this definition, $k$-linked implies $k$-ordered. So, $6$-connected does not imply $2$-linked.
$endgroup$
– Tony Huynh
Apr 5 at 11:59
$begingroup$
It's obvious that your new definition (where vertices are not necessarily distinct) implies the original one, but why are the two equivalent?
$endgroup$
– user137930
Apr 5 at 12:36
|
show 3 more comments
$begingroup$
Thanks! Is there a better known bound for $f(k)$ than $20$ in the case $k=2$? It doesn't seem to be in the paper.
$endgroup$
– user137930
Apr 5 at 11:06
$begingroup$
Yes, $7$-connected implies $2$-linked. Actually $7$-connected implies that for every set of $4$ vertices $a,b,c,d$ there is a cycle containing $a,b,c,d$ (in that order). This is stronger than $2$-linked. See arxiv.org/abs/1808.05124
$endgroup$
– Tony Huynh
Apr 5 at 11:11
$begingroup$
Thanks again. One more question: Is it known that $6$-connected does not imply $2$-linked? The paper mentions that $7$ is tight for the cycle property, but since the path property is weaker this is unclear.
$endgroup$
– user137930
Apr 5 at 11:32
$begingroup$
Actually, the definition I used for $k$-linked is equivalent to the version where $s_1, dots, s_k, t_1, dots, t_k$ are not necessarily distinct, but the paths are required to be internally-disjoint. With this definition, $k$-linked implies $k$-ordered. So, $6$-connected does not imply $2$-linked.
$endgroup$
– Tony Huynh
Apr 5 at 11:59
$begingroup$
It's obvious that your new definition (where vertices are not necessarily distinct) implies the original one, but why are the two equivalent?
$endgroup$
– user137930
Apr 5 at 12:36
$begingroup$
Thanks! Is there a better known bound for $f(k)$ than $20$ in the case $k=2$? It doesn't seem to be in the paper.
$endgroup$
– user137930
Apr 5 at 11:06
$begingroup$
Thanks! Is there a better known bound for $f(k)$ than $20$ in the case $k=2$? It doesn't seem to be in the paper.
$endgroup$
– user137930
Apr 5 at 11:06
$begingroup$
Yes, $7$-connected implies $2$-linked. Actually $7$-connected implies that for every set of $4$ vertices $a,b,c,d$ there is a cycle containing $a,b,c,d$ (in that order). This is stronger than $2$-linked. See arxiv.org/abs/1808.05124
$endgroup$
– Tony Huynh
Apr 5 at 11:11
$begingroup$
Yes, $7$-connected implies $2$-linked. Actually $7$-connected implies that for every set of $4$ vertices $a,b,c,d$ there is a cycle containing $a,b,c,d$ (in that order). This is stronger than $2$-linked. See arxiv.org/abs/1808.05124
$endgroup$
– Tony Huynh
Apr 5 at 11:11
$begingroup$
Thanks again. One more question: Is it known that $6$-connected does not imply $2$-linked? The paper mentions that $7$ is tight for the cycle property, but since the path property is weaker this is unclear.
$endgroup$
– user137930
Apr 5 at 11:32
$begingroup$
Thanks again. One more question: Is it known that $6$-connected does not imply $2$-linked? The paper mentions that $7$ is tight for the cycle property, but since the path property is weaker this is unclear.
$endgroup$
– user137930
Apr 5 at 11:32
$begingroup$
Actually, the definition I used for $k$-linked is equivalent to the version where $s_1, dots, s_k, t_1, dots, t_k$ are not necessarily distinct, but the paths are required to be internally-disjoint. With this definition, $k$-linked implies $k$-ordered. So, $6$-connected does not imply $2$-linked.
$endgroup$
– Tony Huynh
Apr 5 at 11:59
$begingroup$
Actually, the definition I used for $k$-linked is equivalent to the version where $s_1, dots, s_k, t_1, dots, t_k$ are not necessarily distinct, but the paths are required to be internally-disjoint. With this definition, $k$-linked implies $k$-ordered. So, $6$-connected does not imply $2$-linked.
$endgroup$
– Tony Huynh
Apr 5 at 11:59
$begingroup$
It's obvious that your new definition (where vertices are not necessarily distinct) implies the original one, but why are the two equivalent?
$endgroup$
– user137930
Apr 5 at 12:36
$begingroup$
It's obvious that your new definition (where vertices are not necessarily distinct) implies the original one, but why are the two equivalent?
$endgroup$
– user137930
Apr 5 at 12:36
|
show 3 more comments
user137930 is a new contributor. Be nice, and check out our Code of Conduct.
user137930 is a new contributor. Be nice, and check out our Code of Conduct.
user137930 is a new contributor. Be nice, and check out our Code of Conduct.
user137930 is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to MathOverflow!
- 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%2fmathoverflow.net%2fquestions%2f327207%2fdisjoint-paths-between-four-vertices%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
1
$begingroup$
Wouldn't the vertex connectivity have to be at least $3$? If the graph $G$ can be disconnected by removing two vertices $a,b$, and if $c,d$ are in different components of $G-a-b$
$endgroup$
– bof
Apr 5 at 9:43