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.
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'$:
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?