What kind of graph is this? Hamiltonian by association?

37 Views Asked by At

Here is an example of a connected cycle using the edges: $ABC-BCD-BCE-CDE-BDE-ABE-ACE-ADE-ACD$

Here $ABC$ shares $BC$ with $BCD$, $BCD$ shares $BC$ with $BCE$, ... , $ACD$ shares $AC$ with $ABC$. These shared edges converted to vertices themselves form a Hamiltonian cycle and path by association, but these edges are not directed so they can't be drawn in a path. A hamiltonian path is a path which visits each vertex only once.

These can form hamiltonian paths and cycles as subsets, but the whole set does not give a Hamiltonian path. I'm wondering if there's a name for a graph like this?

1

There are 1 best solutions below

0
On

You could think of this as some very complicated and hard-to-define object in a graph where $A,B,C,D,E$ are vertices and $AB, AC, AD, \dots, CE, DE$ are edges. But that's not very enlightening.

Instead, you could take your graph to have $$ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE$$ as its vertices, with an edge between two triples that have two letters in common. This graph happens to be isomorphic to the complement of the Petersen graph.

If you do this, then your sequence is just an ordinary Hamiltonian cycle in this graph.