4
$\begingroup$

I am currently developing TSP heuristics that aim at symmetrically reducing the original, complete and undirected graph.

The overarching rationale is that the reduction is done via a sequence of regular graphs. In view of Tutte's counterexample to Tait's conjecture, it is clear that generating a sequence of maximally vertex-connected graphs need not produce a Hamiltonian tour ($=$Hamiltonian cycle) in the end.

The rationale that I am trying to follow is that the intermediate graphs should also be vertex-symmetric in other respects than just vertex-connectivity (in Tutte's counter-example graph the vertices are not equal with respect to the size of adjacent "facets").

When trying to guarantee that the intermediate regular graphs are also symmetric in some other specific sense, it was found that the following directed graph could help accomplish that:

Question:

Let $G\left( V,E\right)$ be the given graph with vertices $v\in V$ and edges $e\in E$, construct from it the directed graph $H\left( N=V\cup E,A\subset N\times N\right)$ of nodes $n\in N$ and arcs $a\in A$, in which w.l.o.g. the set of arcs is directed from images of vertices to images of incident edges and from images of edges to images of non-incident vertices; i.e. $A=\lbrace\left(v_j,e_{ij}\right)\rbrace\cup\lbrace\left(v_j,e_{jk}\right)\rbrace\cup\lbrace\left(e_{ij},v_k\right)\rbrace$

Has that kind of "derived" graph $H\left(N,A\right)$ already appeared in mathematical publications and what is it called (it has some aspects of an incidence graph, but also of an adjacency graph)?

$\endgroup$
  • $\begingroup$ Dear @Manfred Weis, the only thing that I do not think I conceptually understand 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:40
  • $\begingroup$ Unrelated to your question, yet related to what I interpret your preliminary explanations are getting at: you might like to have a look at lower bounds proved in Journal of Combinatorial Theory, Series B Volume 41, Issue 1, August 1986, Pages 17-26, and upper bounds proved in: Grünbaum, B. and Motzkin, T. S. (1962), Longest Simple Paths in Polyhedral Graphs. Journal of the London Mathematical Society, s1-37: 152–160 $\endgroup$ – Peter Heinig Aug 9 '17 at 18:53
  • $\begingroup$ Dear @Manfred Weis, re the question itself: while the meaning is clear, it would be clearer and more usual to write $A = \{ (v,e)\in V\times E \colon v\in e \} \cup \{ (e,v) \colon \neg (v\in e) \}$. The use of the subscripted $v$ and $e$ is ususual and confusing. In particular, mentioning the vertex-to-incident-edge-arcs twice can be confusing to readers: the edges of the original graph are not oriented, so doubly mentioning them is redundant. $\endgroup$ – Peter Heinig Aug 9 '17 at 19:14
  • $\begingroup$ Dear @Manfred Weis: also, in the question-statement, "w.l.o.g. the set of arcs is directed from images of vertices to images of adjacent edges" reads unusual in two respects: (0) why 'without loss of generality here' here? no assumption is made, just a definition, no need for w.l.o.g. (1) to say that 'the set of arcs is directed' sounds wrong: the set itself does not get directed, rather, each arc is directed. $\endgroup$ – Peter Heinig Aug 9 '17 at 19:30
  • $\begingroup$ @PeterHeinig: thanks for the feedback and illustration in your answer. Regarding my lack in proficiency in terminology - I am not a professional mathematician, but my expression "vertex-symmetric" was chosen consciously, because that also covers the outcome of algorithms that operate on weighted graphs and yield a set of edges; if every such algorithm yields the same number and multiplicities of edges adjacent to a vertex for every vertex, then I call the weighted graph vertex-symmetric. But I see that I have to come up with a precise definition. $\endgroup$ – Manfred Weis Aug 10 '17 at 4:52
4
$\begingroup$

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 incidence4 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 simply0 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, usual2 less pleonastic3, 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-colorable 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:

enter image description here

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

enter image description here

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)

enter image description here

Coxeter introduces the Levi graph here:

Coxeter

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:

enter image description here

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).

$\endgroup$
3
$\begingroup$

Not an answer, yet too large for the comment box and thought to be useful for others to quickly parse the slightly unusual formalism in the OP: the OP asks for literature references and usual technical terms for the class function with domain the class of all simple undirected graphs and codomain the class of all oriented complete bipartite graphs which, in particular, does what is represented by the following:

enter image description here

       enter image description here

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.