**Short answer.** Your question, strictly construed, does not have a noteworthy answer (I think), and there is good reason that it doesn't: your graph $H$ 'is'^{1 } just the Levi graph(=bipartite incidence^{4} graph) of $G$. Using directed edges to encode the non-incidences is *redundant* because in an incidence graph (at least if you are working in material set theory) the vertices are usually meaningfully labelled by the very constituents of the original incidence structure, so all the information about the original not-necessarily bipartite graph is still there, *even if you refrain from adding edges for ***non**-incidences. In a sense, if you start adding edges for non-incidences into a Levi graph, you spoil it, and then have to make amends by adding **all** the edges, and then **start over** with the encoding of your original graph, e.g. by equipping it with *direction*, like you did. In that sense, this is overly complicated. (I recognize that you may have private reasons to insist that $H$ have the type 'digraph', I just do not know these reasons.)

If you insist for whatever reasons that the result of your 'derived graph' *be a digraph*, then (I think) there does not exist a noteworthy literature reference.

**Recommendation.** Re you comment

[...] I see that I have to come up with a precise definition.

If you do not insist that the result of you operation be a "digraph" (in the sense of e.g. the monograph of Bang-Jensen and Gutin), then *you do not need to "come up" with a definition*. Then it is sufficient to simply^{0} say

- For any undirected simple graph $G=(V,E)$, let $W(G)$ be the Levi graph ($=$ bipartite incidence graph) of $G$. (I.e. $W(G)$ has vertex set $V\cup E$ and undirected edges precisely the 2-sets $\{v,e\}$ with $v\in e$.) ${\qquad}$ (LG)

If you insist that the result be a digraph, then that's another matter, and *then you may use the definition you already gave*. (I did not say said definition of yours was imprecise, it was merely *very* usually written, to the point of being almost-wrong at places.)

My recommendations would be to try *to keep reasonably close to usual graph-theoretic notation*, rather than "to come up" with something new. Of course you have a right to unusual notation, it will simply make it less likely that you will be understood.

A. Weil put it well in his textbook "Foundations of Algebraic Geometry", American Mathematical Society, 1946, Introduction:

in a treatment, of this kind, particular attention must be and has been given to the language and, the definitions. Of course every mathematician has a right to his own language - at the risk of not being understood; and the use sometimes made, of this right by our contemporaries almost suggests that the same fate is being prepared for mathematics as once befell, at Babel, another of man's great achievements. A choice between equivalent definitions is of small moment, and two theories which consist of the same theorems are to be regarded as identical, whatever their starting points. But in such a subject as algebraic geometry, where earlier authors left many terms incompletely defined, and were wont to make (sometimes implicitly) assumptions from which we wish to be free, all terms have to be defined anew, and to attach precise meanings to them is a task not unworthy of our most solicitous attention. Our chief object here must be to conserve and complete the edifice bequeathed to us by our predecessors.

which reads eerily relevant to some parts of mathematics today.
(Note also: somewhat ironically, despite the author's well-meaning attempt, his language for algebraic geometry has largely been replaced by the one from the EGA and SGA.)

**Detailed answer.**

(0) Your question *does not have an answer if very strictly construed* to mean that you are asking for a *usual* term and **a notable treatment of the use of directed complete bipartite graphs as incidence-graph-like auxiliary graphs**. In other words, your question does not have an answer if you insist that the literature reference (0.0) is noteworthy, (0.1) match your specifications up to and including the *data-types* you chose.

Yet: there is an equivalent definition and you should use that (I think) *unless you have reasons to insist that the result of your operation be a digraph*.

(1) Beware that in the literature the following distinction is often glossed over: (1.0) "abstract incidence graph of a given undirected simple graph" in the strictest sense (i.e., said incidence graph is again *a graph*, no further decorations,) and (2.1) "incidence graph in which the vertices **are** still the parts of the given original, so that no information is lost".

Authors sometimes only give the definition of the incidence graph $I(G)$, in terms of the (names of the) vertices and edges of the given graph $G$, but do not say whether they assume that the vertices are labelled by the data by which $G$ was given.

More clearly, formally, I think one can meaningfully distinguish theh following.
Let $G=(V,E)$ be a given undirected simple and, as mathematician working with material set theory are wont to say, 'labelled' graph. That is, $G$ is a graph as e.g. in Diestel, Graph Theory, 4th ed.

Then

the graph $W(G)$ from (LG) above is again a such an undirected simple labelled graph

$W(G)$ is *not* a 2-colored graph. That is another type: a 2-colored graph is a pair consisting of a graph $G$ and a specified set-map $c\colon V(G)\rightarrow S$ where $S$ is a 2-element set.

$W(G)$ always *is* a 2-colorable graph. That is evident.

$W(G)$ admits a 'canonical' (which, luckily, is a not a formally defined term, leaving some leeway of expression) 2-coloring $c$, namely the unique set-map $c\colon V(W(G))\rightarrow\{V,E\}$ with $c(v)=V$ and $c(e)=E$, i.e., the two-element color-set used here is $\{V,E\}$, a set which exists on account of the Axiom of Pairing of the Zermelo-Fraenkel axioms.

This is a subtle variant of the labelled-vs-unlabelled graph distinction: while both these terms are reasonably standardly defined, there is no standard definition for "labelled graph with labels that we care about", so to speak.

Please note:

many mathematicians would wince at spelling out the above, and in particularl at **'coloring' vertices by a set containing them**, though probably there is nothing wrong with that logically

alternatives to the above are either to make *two arbitrary choices*, namely (0) which two-element set to use for the vertex-coloring, (1) which of the two elements of the arbitrarily chosen two-set to use for the vertex-coloring

category theory offers an alternative to formalize such ideas, in particular, you might find it useful (your mileage may vary) to use category theory to formalize you TSP heuristic and in particular your operation $H$.

(3) The graph $H(N,A)$, to use use your notation (that I warn you against), contains (and with an obvious encoding) the same information as what is usually called the **bipartite incidence graph** (shorter, usual^{2} less pleonastic^{3}, yet also less descriptive term: Levi graph) of the graph $G$, with $G$ being viewed as an incidence structure $(V,E,I)$ having the (elements of the) set $V$ for its points, the (elements of the) set $E$ for its lines, and $I\subseteq V\times E$ given by $(v,e)\in I$ $\Leftrightarrow$ $v\in e$

## Footnotes

^{0} Please be careful though: often, even more often than not I would say, *in the literature a Levi graph is considered to be a 2-colored graph* (not to be confused with 2-color*able* graph). In that sense, strictly speaking **a Levi graph in the literature, unlike in the suggestion above, is often not a graph** in any of the usual senses of 'graph' whihch *never* allow attaching custom data to vertices, **a Levi graph is often, unlike in my suggestion above, considered to be a 2-colored graph**. Example from the the peer reviewed literature is
Dragan Marušič,Tomaž Pisanski, Steve Wilson: European Journal of Combinatorics, Volume 26, Issues 3–4, April–May 2005, Pages 377-385, wherein on p. 378-379 one finds:

and the illustration (which also illustrates the Coxeter-citation given in this answer, by the way)

So, if the precise formalization matters to you, it will be necessary to watch out for whether Levi graph is used to mean 'bicolored bipartite incidence graph' or 'bipartite incidence graph'($=$incidence graph)$\subset$(class of graphs).

^{1} In a rather informal sense of 'is', similar to 'is equivalent to'. To give a precise sense to 'is equivalent to', one *could* take the following route:

- first of all, agree that the following approach is 'the' right one (an agreement which is already hard enough to reach),
- then agree which 'category $\mathsf{C}$ of undirected simple graphs' to use (and there are several such),
- then agree upon a category $\mathsf{C}_0$ having as objects
*bipartite digraphs*,
- then agree upon a category $\mathsf{C}_1$ having as objects
*2-colored bipartite undirected simple graphs*,
- define a functor $F_0\colon\mathsf{C}\rightarrow\mathsf{C}_0$ whose object-class-function equals the class-function adumbrated in the OP (in short: extend your $H$-operation to a functor),
- then define a functor $F_1\colon\mathsf{C}\rightarrow\mathsf{C}_1$ whose
object-class-function takes any undirected simple graph to its vertex-edge-Levi-graph,
- finally prove that $F_0$ and $F_1$ are isomorphic functors.

While such an approach is very useful, there *does not exist an agreement how to carry it out*. No such agreement exists, and probably *cannot exist in view of insufficient criteria how to decide what is essential for you*. It does not seem worthwhile to get into an argument about it.

^{2} To give an early example of Levi graphs being used let met cite H. S. M. Coxeter, *Self-dual configurations and regular graphs*, Bull. Amer. Math. Soc., Volume 56, Number 5 (1950), 413-455, wherein on p. 414 we have the following illustration (retouched to hide distracting information)

Coxeter introduces the Levi graph here:

^{ 3 } _{ The (very usual) technical compound term "bipartite incidence graph" is the same type of pleonasm as "bicyclic mountain bike". An "incidence graph" (to me at least, and to many others) is always bipartite. Therefore, "bipartite incidence graph" is pleonastic. However, neither the compound "incidence graph", nor "bipartite graph" are pleonastic terms, only upon taking the sort-of-union $\{$ incidence graph $\}$ $\cup$ $\{$ bipartite graph $\}$ $\approx$ $\{$ bipartite incidence graph $\}$ one ends up with a pleonasm. }

Similarly,

'mountain bike' lexically exists.

The compound 'mountain bike' is not pleonastic at all; by far not every bike is a mountain bike, in any reasonable sense.

The compound 'bicyclic mountain bike' is pleonastic, in a reasonably clear sense: no usual mountain bike has a number of wheels other than 2.

There exist bikes which are non-bicyclic, in that there exist *unicycles*. So this is an example of what I would call an

'a n N'-pleonasm

Definition. An 'a n N' pleonasm is a compound wherein 'a' is an adjective, 'N' is a noun, 'n N' must be a lexically existant noun compound, 'n N' must be *non-pleonastic*, and 'a N' must be reasonably meaningful and *non-pleonastic* too, while 'a n N' itself must be reasonably meaningful yet pleonastic *in that every 'n N' is 'a'*.

Again, it is only pleonastic to add the 'a' to the 'n N'. It is not pleonastic to add 'a' to 'N', nor to add 'n' to 'N'. (Note that 'bicyclic bike', while unusual, is not pleonastic, and appropriate in certain contexts, in view of unicycles or training wheels.)

^{4} _{ To give an example from the literature that the notation $v\in e$ I recommended elsewhere is usual, consider e.g. Diestel, Graph Theory, 4th edition, p. 2, which gives a way of putting it which is usual nowadays:}

Incidentally, this also gives one more *reason* why the notation $G(V,E)$ in the original OP is not to be recommended: it is similar to $E(X,Y)$, hence will read to some as if you had named an *edge set* by '$G$', a vertex by '$V$' and **another vertex set** by '$E$', which is confusing (to me).

conceptuallyunderstand about the preliminary explanations is "should also be vertex-symmetric in other respects than just vertex-connectivity". This (to me) read like " 'vertex-connectivity' is a sub-concept of 'vertex-symmetric' " which (to me) is incomprehensible in two respects simultaneously: (0) "vertex-symmetric" is not a usual technical term in graph theory (as opposed to e.g. "vertex-transitive, or variants thereof, which would be usual), and (1) connectivity is not naturally related to symmetry. Would you please clarify? $\endgroup$ – Peter Heinig Aug 9 '17 at 18:40Longest Simple Paths in Polyhedral Graphs. Journal of the London Mathematical Society, s1-37: 152–160 $\endgroup$ – Peter Heinig Aug 9 '17 at 18:53twicecan be confusing to readers: the edges of the original graph arenotoriented, so doubly mentioning them is redundant. $\endgroup$ – Peter Heinig Aug 9 '17 at 19:14setitself does not get directed, rather, each arc is directed. $\endgroup$ – Peter Heinig Aug 9 '17 at 19:30