In my recreational occupation with the TSP I encountered a family of graphs, which I would like to call "Möbius Sponges" because they generalize the Möbius Ladder graphs in a way, that may provide an answer for the hardness of the TSP.

Those Möbius Sponges are connected, very regular while allowing for randomness and provide a roadmap for the transition from complete graphs to Hamilton cycles.


  • what kind of graph properties (e.g. spectrum, automorphism group, etc.) are the (most) interesting ones to check, provided time and resources for checking are limited and, what are the arguments in favor of specific suggestions?

  • Apart from that, what would be the most appropriate way to communicate a description of and/or algorithm for generating the Möbius Sponges?


Your Answer

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

Browse other questions tagged or ask your own question.