Secret Santa graph with non-clique friend group - name of this problem/graph?
$begingroup$
Background:
Secret Santa is a game where a group of mutual friends are randomly assigned a partner to select a gift for.
We can represent this friend group with an undirected graph $G(V,E)$, where each vertex $v in V$ represents a friend, and each edge $e in E$ represents a friendship.
Traditionally, $G$ is a clique: There is one edge for each pair of friends. We define the Secret Santa graph $G'(V,E')$, a directed graph where there is one incoming and one outgoing edge per node.
Example of such a traditional G and a possible associated G':
G with clique size 4 on the left; G' on the right.
New problem
Now consider a non-clique $G$. This could arise in real life due to restrictions (e.g. Friends $a$ and $d$ are partners and should not buy for one another, or they do not know one another.) We want to generate a possible Secret Santa graph $G'$ as defined above, if possible.
Example of such a graph $G$ and a possible $G'$:
A non-clique G with an example G'.
We can also friend graphs $G$ that have no Secret Santa graph $G'$:
A graph G that cannot have a Secret Santa graph G'
Question
Are there names for such Secret Santa graphs $G'$, when the friend graph $G$ is not necessarily a clique? If so, are there any papers with algorithms and runtimes on how to find such graphs?
graph-theory
asked Nov 30 '18 at 18:16
tpepin96tpepin96
134
$endgroup$
|
show 1 more comment
$begingroup$
Background:
Secret Santa is a game where a group of mutual friends are randomly assigned a partner to select a gift for.
We can represent this friend group with an undirected graph $G(V,E)$, where each vertex $v in V$ represents a friend, and each edge $e in E$ represents a friendship.
Traditionally, $G$ is a clique: There is one edge for each pair of friends. We define the Secret Santa graph $G'(V,E')$, a directed graph where there is one incoming and one outgoing edge per node.
Example of such a traditional G and a possible associated G':
G with clique size 4 on the left; G' on the right.
New problem
Now consider a non-clique $G$. This could arise in real life due to restrictions (e.g. Friends $a$ and $d$ are partners and should not buy for one another, or they do not know one another.) We want to generate a possible Secret Santa graph $G'$ as defined above, if possible.
Example of such a graph $G$ and a possible $G'$:
A non-clique G with an example G'.
We can also friend graphs $G$ that have no Secret Santa graph $G'$:
A graph G that cannot have a Secret Santa graph G'
Question
Are there names for such Secret Santa graphs $G'$, when the friend graph $G$ is not necessarily a clique? If so, are there any papers with algorithms and runtimes on how to find such graphs?
graph-theory
asked Nov 30 '18 at 18:16
tpepin96tpepin96
134
$endgroup$
1
$begingroup$
I'm somewhat confused by your first example: I don't think your $G'$ is valid: $c$ is receiving two presents and giving one, while $b$ is giving two, and receiving one. Surely this is something that you want to avoid? At which point, your Secret Santa graphs are simply unions of directed cycle graphs, and the $G$ which produce such $G'$ are precisely those that can, by removing some edges, be made into a disjoint union of digraphs with at least two vertices, each of which has a Hamiltonian cycle.
$endgroup$
– user3482749
Nov 30 '18 at 18:25
$begingroup$
My apologies, you're entirely right. I fixed the graph. But this answers my question - it looks like a "Hamiltonian cycle" is exactly what I am looking for.
$endgroup$
– tpepin96
Nov 30 '18 at 18:56
1
$begingroup$
There is a "Secret Santa" graph if and only if the original graph has a disjoint set of cycles that covers all the vertices. I don't know whether there's a name for these graphs or not.
$endgroup$
– saulspatz
Nov 30 '18 at 19:05
$begingroup$
@saulspatz: Except there may be Santa loops of length 2. I guess this suggests that the definition in the question is maybe suboptimal, and we should be looking at subgraphs of directed graphs instead (whereupon your characterization is true).
$endgroup$
– Micah
Nov 30 '18 at 19:37
$begingroup$
@Micah Good point. I didn't think of that.
$endgroup$
– saulspatz
Nov 30 '18 at 19:42
|
show 1 more comment
$begingroup$
Background:
Secret Santa is a game where a group of mutual friends are randomly assigned a partner to select a gift for.
We can represent this friend group with an undirected graph $G(V,E)$, where each vertex $v in V$ represents a friend, and each edge $e in E$ represents a friendship.
Traditionally, $G$ is a clique: There is one edge for each pair of friends. We define the Secret Santa graph $G'(V,E')$, a directed graph where there is one incoming and one outgoing edge per node.
Example of such a traditional G and a possible associated G':
G with clique size 4 on the left; G' on the right.
New problem
Now consider a non-clique $G$. This could arise in real life due to restrictions (e.g. Friends $a$ and $d$ are partners and should not buy for one another, or they do not know one another.) We want to generate a possible Secret Santa graph $G'$ as defined above, if possible.
Example of such a graph $G$ and a possible $G'$:
A non-clique G with an example G'.
We can also friend graphs $G$ that have no Secret Santa graph $G'$:
A graph G that cannot have a Secret Santa graph G'
Question
Are there names for such Secret Santa graphs $G'$, when the friend graph $G$ is not necessarily a clique? If so, are there any papers with algorithms and runtimes on how to find such graphs?
graph-theory
asked Nov 30 '18 at 18:16
tpepin96tpepin96
134
$endgroup$
Background:
Secret Santa is a game where a group of mutual friends are randomly assigned a partner to select a gift for.
We can represent this friend group with an undirected graph $G(V,E)$, where each vertex $v in V$ represents a friend, and each edge $e in E$ represents a friendship.
Traditionally, $G$ is a clique: There is one edge for each pair of friends. We define the Secret Santa graph $G'(V,E')$, a directed graph where there is one incoming and one outgoing edge per node.
Example of such a traditional G and a possible associated G':
G with clique size 4 on the left; G' on the right.
New problem
Now consider a non-clique $G$. This could arise in real life due to restrictions (e.g. Friends $a$ and $d$ are partners and should not buy for one another, or they do not know one another.) We want to generate a possible Secret Santa graph $G'$ as defined above, if possible.
Example of such a graph $G$ and a possible $G'$:
A non-clique G with an example G'.
We can also friend graphs $G$ that have no Secret Santa graph $G'$:
A graph G that cannot have a Secret Santa graph G'
Question
Are there names for such Secret Santa graphs $G'$, when the friend graph $G$ is not necessarily a clique? If so, are there any papers with algorithms and runtimes on how to find such graphs?
graph-theory
graph-theory
asked Nov 30 '18 at 18:16
tpepin96tpepin96
134
asked Nov 30 '18 at 18:16
tpepin96tpepin96
134
edited Nov 30 '18 at 18:55
tpepin96
asked Nov 30 '18 at 18:16
tpepin96tpepin96
134
asked Nov 30 '18 at 18:16
tpepin96tpepin96
134
asked Nov 30 '18 at 18:16
tpepin96tpepin96
134
134
1
$begingroup$
I'm somewhat confused by your first example: I don't think your $G'$ is valid: $c$ is receiving two presents and giving one, while $b$ is giving two, and receiving one. Surely this is something that you want to avoid? At which point, your Secret Santa graphs are simply unions of directed cycle graphs, and the $G$ which produce such $G'$ are precisely those that can, by removing some edges, be made into a disjoint union of digraphs with at least two vertices, each of which has a Hamiltonian cycle.
$endgroup$
– user3482749
Nov 30 '18 at 18:25
$begingroup$
My apologies, you're entirely right. I fixed the graph. But this answers my question - it looks like a "Hamiltonian cycle" is exactly what I am looking for.
$endgroup$
– tpepin96
Nov 30 '18 at 18:56
1
$begingroup$
There is a "Secret Santa" graph if and only if the original graph has a disjoint set of cycles that covers all the vertices. I don't know whether there's a name for these graphs or not.
$endgroup$
– saulspatz
Nov 30 '18 at 19:05
$begingroup$
@saulspatz: Except there may be Santa loops of length 2. I guess this suggests that the definition in the question is maybe suboptimal, and we should be looking at subgraphs of directed graphs instead (whereupon your characterization is true).
$endgroup$
– Micah
Nov 30 '18 at 19:37
$begingroup$
@Micah Good point. I didn't think of that.
$endgroup$
– saulspatz
Nov 30 '18 at 19:42
|
show 1 more comment
1
$begingroup$
I'm somewhat confused by your first example: I don't think your $G'$ is valid: $c$ is receiving two presents and giving one, while $b$ is giving two, and receiving one. Surely this is something that you want to avoid? At which point, your Secret Santa graphs are simply unions of directed cycle graphs, and the $G$ which produce such $G'$ are precisely those that can, by removing some edges, be made into a disjoint union of digraphs with at least two vertices, each of which has a Hamiltonian cycle.
$endgroup$
– user3482749
Nov 30 '18 at 18:25
$begingroup$
My apologies, you're entirely right. I fixed the graph. But this answers my question - it looks like a "Hamiltonian cycle" is exactly what I am looking for.
$endgroup$
– tpepin96
Nov 30 '18 at 18:56
1
$begingroup$
There is a "Secret Santa" graph if and only if the original graph has a disjoint set of cycles that covers all the vertices. I don't know whether there's a name for these graphs or not.
$endgroup$
– saulspatz
Nov 30 '18 at 19:05
$begingroup$
@saulspatz: Except there may be Santa loops of length 2. I guess this suggests that the definition in the question is maybe suboptimal, and we should be looking at subgraphs of directed graphs instead (whereupon your characterization is true).
$endgroup$
– Micah
Nov 30 '18 at 19:37
$begingroup$
@Micah Good point. I didn't think of that.
$endgroup$
– saulspatz
Nov 30 '18 at 19:42
1
1
$begingroup$
I'm somewhat confused by your first example: I don't think your $G'$ is valid: $c$ is receiving two presents and giving one, while $b$ is giving two, and receiving one. Surely this is something that you want to avoid? At which point, your Secret Santa graphs are simply unions of directed cycle graphs, and the $G$ which produce such $G'$ are precisely those that can, by removing some edges, be made into a disjoint union of digraphs with at least two vertices, each of which has a Hamiltonian cycle.
$endgroup$
– user3482749
Nov 30 '18 at 18:25
$begingroup$
I'm somewhat confused by your first example: I don't think your $G'$ is valid: $c$ is receiving two presents and giving one, while $b$ is giving two, and receiving one. Surely this is something that you want to avoid? At which point, your Secret Santa graphs are simply unions of directed cycle graphs, and the $G$ which produce such $G'$ are precisely those that can, by removing some edges, be made into a disjoint union of digraphs with at least two vertices, each of which has a Hamiltonian cycle.
$endgroup$
– user3482749
Nov 30 '18 at 18:25
$begingroup$
My apologies, you're entirely right. I fixed the graph. But this answers my question - it looks like a "Hamiltonian cycle" is exactly what I am looking for.
$endgroup$
– tpepin96
Nov 30 '18 at 18:56
$begingroup$
My apologies, you're entirely right. I fixed the graph. But this answers my question - it looks like a "Hamiltonian cycle" is exactly what I am looking for.
$endgroup$
– tpepin96
Nov 30 '18 at 18:56
1
1
$begingroup$
There is a "Secret Santa" graph if and only if the original graph has a disjoint set of cycles that covers all the vertices. I don't know whether there's a name for these graphs or not.
$endgroup$
– saulspatz
Nov 30 '18 at 19:05
$begingroup$
There is a "Secret Santa" graph if and only if the original graph has a disjoint set of cycles that covers all the vertices. I don't know whether there's a name for these graphs or not.
$endgroup$
– saulspatz
Nov 30 '18 at 19:05
$begingroup$
@saulspatz: Except there may be Santa loops of length 2. I guess this suggests that the definition in the question is maybe suboptimal, and we should be looking at subgraphs of directed graphs instead (whereupon your characterization is true).
$endgroup$
– Micah
Nov 30 '18 at 19:37
$begingroup$
@saulspatz: Except there may be Santa loops of length 2. I guess this suggests that the definition in the question is maybe suboptimal, and we should be looking at subgraphs of directed graphs instead (whereupon your characterization is true).
$endgroup$
– Micah
Nov 30 '18 at 19:37
$begingroup$
@Micah Good point. I didn't think of that.
$endgroup$
– saulspatz
Nov 30 '18 at 19:42
$begingroup$
@Micah Good point. I didn't think of that.
$endgroup$
– saulspatz
Nov 30 '18 at 19:42
|
show 1 more comment
1 Answer
1
active
oldest
votes
$begingroup$
These notes discuss this problem in the directed graph case. Note that this solves the length-$2$ issue discussed in the comments, as well as allowing for asymmetric friendships if necessary. (For example, if Alice gave to Bob last year, you might want to disallow that from happening again while still allowing Bob to give to Alice.) If all friendships are symmetric, that just means we have edges in both directions.
The idea is as follows. Given a digraph $G$, we form a bipartite graph $E$ whose vertex set is $V(G) times {L, R}$. If there is a directed edge in $G$ from $v$ to $w$, we put an edge in $E$ from $v_L$ to $w_R$. Then partitions of $G$ into vertex-disjoint cycles correspond to perfect matchings on $E$, for which there are good polynomial-time algorithms (the classic one being the Ford-Fulkerson algorithm, but there are also faster options if necessary).
answered Dec 1 '18 at 15:04
MicahMicah
29.8k1364106
$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%2f3020433%2fsecret-santa-graph-with-non-clique-friend-group-name-of-this-problem-graph%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$
These notes discuss this problem in the directed graph case. Note that this solves the length-$2$ issue discussed in the comments, as well as allowing for asymmetric friendships if necessary. (For example, if Alice gave to Bob last year, you might want to disallow that from happening again while still allowing Bob to give to Alice.) If all friendships are symmetric, that just means we have edges in both directions.
The idea is as follows. Given a digraph $G$, we form a bipartite graph $E$ whose vertex set is $V(G) times {L, R}$. If there is a directed edge in $G$ from $v$ to $w$, we put an edge in $E$ from $v_L$ to $w_R$. Then partitions of $G$ into vertex-disjoint cycles correspond to perfect matchings on $E$, for which there are good polynomial-time algorithms (the classic one being the Ford-Fulkerson algorithm, but there are also faster options if necessary).
answered Dec 1 '18 at 15:04
MicahMicah
29.8k1364106
$endgroup$
add a comment |
$begingroup$
These notes discuss this problem in the directed graph case. Note that this solves the length-$2$ issue discussed in the comments, as well as allowing for asymmetric friendships if necessary. (For example, if Alice gave to Bob last year, you might want to disallow that from happening again while still allowing Bob to give to Alice.) If all friendships are symmetric, that just means we have edges in both directions.
The idea is as follows. Given a digraph $G$, we form a bipartite graph $E$ whose vertex set is $V(G) times {L, R}$. If there is a directed edge in $G$ from $v$ to $w$, we put an edge in $E$ from $v_L$ to $w_R$. Then partitions of $G$ into vertex-disjoint cycles correspond to perfect matchings on $E$, for which there are good polynomial-time algorithms (the classic one being the Ford-Fulkerson algorithm, but there are also faster options if necessary).
answered Dec 1 '18 at 15:04
MicahMicah
29.8k1364106
$endgroup$
add a comment |
$begingroup$
These notes discuss this problem in the directed graph case. Note that this solves the length-$2$ issue discussed in the comments, as well as allowing for asymmetric friendships if necessary. (For example, if Alice gave to Bob last year, you might want to disallow that from happening again while still allowing Bob to give to Alice.) If all friendships are symmetric, that just means we have edges in both directions.
The idea is as follows. Given a digraph $G$, we form a bipartite graph $E$ whose vertex set is $V(G) times {L, R}$. If there is a directed edge in $G$ from $v$ to $w$, we put an edge in $E$ from $v_L$ to $w_R$. Then partitions of $G$ into vertex-disjoint cycles correspond to perfect matchings on $E$, for which there are good polynomial-time algorithms (the classic one being the Ford-Fulkerson algorithm, but there are also faster options if necessary).
answered Dec 1 '18 at 15:04
MicahMicah
29.8k1364106
$endgroup$
These notes discuss this problem in the directed graph case. Note that this solves the length-$2$ issue discussed in the comments, as well as allowing for asymmetric friendships if necessary. (For example, if Alice gave to Bob last year, you might want to disallow that from happening again while still allowing Bob to give to Alice.) If all friendships are symmetric, that just means we have edges in both directions.
The idea is as follows. Given a digraph $G$, we form a bipartite graph $E$ whose vertex set is $V(G) times {L, R}$. If there is a directed edge in $G$ from $v$ to $w$, we put an edge in $E$ from $v_L$ to $w_R$. Then partitions of $G$ into vertex-disjoint cycles correspond to perfect matchings on $E$, for which there are good polynomial-time algorithms (the classic one being the Ford-Fulkerson algorithm, but there are also faster options if necessary).
answered Dec 1 '18 at 15:04
MicahMicah
29.8k1364106
edited Dec 1 '18 at 15:17
answered Dec 1 '18 at 15:04
MicahMicah
29.8k1364106
answered Dec 1 '18 at 15:04
MicahMicah
29.8k1364106
answered Dec 1 '18 at 15:04
MicahMicah
29.8k1364106
29.8k1364106
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%2f3020433%2fsecret-santa-graph-with-non-clique-friend-group-name-of-this-problem-graph%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$
I'm somewhat confused by your first example: I don't think your $G'$ is valid: $c$ is receiving two presents and giving one, while $b$ is giving two, and receiving one. Surely this is something that you want to avoid? At which point, your Secret Santa graphs are simply unions of directed cycle graphs, and the $G$ which produce such $G'$ are precisely those that can, by removing some edges, be made into a disjoint union of digraphs with at least two vertices, each of which has a Hamiltonian cycle.
$endgroup$
– user3482749
Nov 30 '18 at 18:25
$begingroup$
My apologies, you're entirely right. I fixed the graph. But this answers my question - it looks like a "Hamiltonian cycle" is exactly what I am looking for.
$endgroup$
– tpepin96
Nov 30 '18 at 18:56
1
$begingroup$
There is a "Secret Santa" graph if and only if the original graph has a disjoint set of cycles that covers all the vertices. I don't know whether there's a name for these graphs or not.
$endgroup$
– saulspatz
Nov 30 '18 at 19:05
$begingroup$
@saulspatz: Except there may be Santa loops of length 2. I guess this suggests that the definition in the question is maybe suboptimal, and we should be looking at subgraphs of directed graphs instead (whereupon your characterization is true).
$endgroup$
– Micah
Nov 30 '18 at 19:37
$begingroup$
@Micah Good point. I didn't think of that.
$endgroup$
– saulspatz
Nov 30 '18 at 19:42