It is well known, that there are two basic kinds of manifolds, orientable and non-orientable ones; the most simple examples being obtained by identifying a pair of opposite sides of a rectangular strip,
- either with parallel orientation, yielding an orientable surface
- or with antiparallel orientation, yielding the unorientable Möbius strip
In graph theory we the Prism graphs and the Möbius Ladder graphs as generalizations of rectangular strips with a pair of opposite sides identified in the two different ways, i.e. without or with a twist.
A common property of both, the Prism graphs and the Möbius Ladder graphs is the following:
both kinds of graphs are a connected collection of 4-cycles, where the edges, that are shared by at least two of the 4-cycles constitute to a perfect matching.
Telling Prism graphs and Möbius Ladder graphs apart can be accomplished by checking connectivity after removing all edges, that are common to at least two 4-cycles: the graph is a Möbius Ladder iff it remains connected after removing those edges.
Now, if we consider Prism graphs and Möbius Ladder graphs, it seems natural to restrict them further to the connected collections of optimal 4-cycles, for which the edges, that are common to at least two of the 4-cycles constitute to a perfect matching.
Lets consider a symmetric TSP instance and a perfect matching $M$ without pairs of edges constituting to the maximum weight matching of the $K_4$ induced by their adjacent vertices (i.e. no pair of edges is crossing).
After removing the edges constituiting to the maximum weight matching of the $K_4$ induced by the vertices adjacet to a pair of edges in $M$ the 4-cycles that contain two edges of $M$ fulfill the criteria for Prism graphs and for Möbius Ladder graphs in weighted graphs, as defined above.
Additionally removing the edges of $M$ can either render the graph disconnected or, leave it connected, whence one may call the graph oriented, resp. unoriented w.r.t. $M$ and, taking it a bit further, if every perfect matching without crossing edges "disconnects" the graph, the graph could simply be called orientable, without refering to specific perfect matchings.
Question:
has that aspect of perfect matchings already been observed and, what are the implications e.g. on the hardness of TSP instances or on the performance of TSP heuristics?
