Disjoint paths between four 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 19 hours ago
user137930user137930
453
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 19 hours ago
user137930user137930
453
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
17 hours ago
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 19 hours ago
user137930user137930
453
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 19 hours ago
user137930user137930
453
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 19 hours ago
user137930user137930
453
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 19 hours ago
user137930user137930
453
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 19 hours ago
user137930user137930
453
asked 19 hours ago
user137930user137930
453
453
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
17 hours ago
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
17 hours ago
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
17 hours ago
$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
17 hours ago
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 16 hours ago
Tony HuynhTony Huynh
19.6k571130
$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
15 hours ago
$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
15 hours ago
$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
15 hours ago
$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
14 hours ago
$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
14 hours ago
|
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 16 hours ago
Tony HuynhTony Huynh
19.6k571130
$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
15 hours ago
$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
15 hours ago
$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
15 hours ago
$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
14 hours ago
$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
14 hours ago
|
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 16 hours ago
Tony HuynhTony Huynh
19.6k571130
$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
15 hours ago
$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
15 hours ago
$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
15 hours ago
$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
14 hours ago
$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
14 hours ago
|
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 16 hours ago
Tony HuynhTony Huynh
19.6k571130
$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 16 hours ago
Tony HuynhTony Huynh
19.6k571130
edited 16 hours ago
answered 16 hours ago
Tony HuynhTony Huynh
19.6k571130
answered 16 hours ago
Tony HuynhTony Huynh
19.6k571130
answered 16 hours ago
Tony HuynhTony Huynh
19.6k571130
19.6k571130
$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
15 hours ago
$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
15 hours ago
$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
15 hours ago
$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
14 hours ago
$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
14 hours ago
|
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
15 hours ago
$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
15 hours ago
$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
15 hours ago
$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
14 hours ago
$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
14 hours ago
$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
15 hours ago
$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
15 hours ago
$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
15 hours ago
$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
15 hours ago
$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
15 hours ago
$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
15 hours ago
$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
14 hours ago
$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
14 hours ago
$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
14 hours ago
$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
14 hours ago
|
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
17 hours ago