Skip to main content
added 80 characters in body
Source Link
Hans-Peter Stricker
  • 9.7k
  • 5
  • 54
  • 113

Hamiltonian cycles (seen as spanning polygons) are interesting for several reasons (only a few of which I am aware of), but especially because not every connected graph has a Hamiltonian cycle (is Hamiltonian), so the characterization of Hamiltonian graphs becomes interesting (see wikipedia article on Hamiltonian paths).

Side note: Each platonic and archimedian solid is Hamiltonian.

What about spanning polytopes, as one possible generalization of Hamiltonian cycles = spanning polygons?

(By "spanning polytope" I mean a spanning subgraph that is the 1-skeleton of a polytope of arbitrary dimension.)

There are connected graphs without spanning polytopes (trees obviously), but there are non-Hamiltonian graphs that have a spanning polytope of dimension d>2, e.g. the Herschel graph.

A google search for "spanning polytope"google search for "spanning polytope" yields only very few and unrelated results, so my question is:

Is there research on this or a related topic, only under another name?

If not so, does this have an obvious - or not so obvious - reason?

Hamiltonian cycles (seen as spanning polygons) are interesting for several reasons (only a few of which I am aware of), but especially because not every connected graph has a Hamiltonian cycle (is Hamiltonian), so the characterization of Hamiltonian graphs becomes interesting (see wikipedia article on Hamiltonian paths).

Side note: Each platonic and archimedian solid is Hamiltonian.

What about spanning polytopes, as one possible generalization of Hamiltonian cycles = spanning polygons?

(By "spanning polytope" I mean a spanning subgraph that is the 1-skeleton of a polytope of arbitrary dimension.)

There are connected graphs without spanning polytopes (trees obviously), but there are non-Hamiltonian graphs that have a spanning polytope of dimension d>2, e.g. the Herschel graph.

A google search for "spanning polytope" yields only unrelated results, so my question is:

Is there research on this or a related topic, only under another name?

If not so, does this have an obvious - or not so obvious - reason?

Hamiltonian cycles (seen as spanning polygons) are interesting for several reasons (only a few of which I am aware of), but especially because not every connected graph has a Hamiltonian cycle (is Hamiltonian), so the characterization of Hamiltonian graphs becomes interesting (see wikipedia article on Hamiltonian paths).

Side note: Each platonic and archimedian solid is Hamiltonian.

What about spanning polytopes, as one possible generalization of Hamiltonian cycles = spanning polygons?

(By "spanning polytope" I mean a spanning subgraph that is the 1-skeleton of a polytope of arbitrary dimension.)

There are connected graphs without spanning polytopes (trees obviously), but there are non-Hamiltonian graphs that have a spanning polytope of dimension d>2, e.g. the Herschel graph.

A google search for "spanning polytope" yields only very few and unrelated results, so my question is:

Is there research on this or a related topic, only under another name?

If not so, does this have an obvious - or not so obvious - reason?

Source Link
Hans-Peter Stricker
  • 9.7k
  • 5
  • 54
  • 113

Spanning polytopes

Hamiltonian cycles (seen as spanning polygons) are interesting for several reasons (only a few of which I am aware of), but especially because not every connected graph has a Hamiltonian cycle (is Hamiltonian), so the characterization of Hamiltonian graphs becomes interesting (see wikipedia article on Hamiltonian paths).

Side note: Each platonic and archimedian solid is Hamiltonian.

What about spanning polytopes, as one possible generalization of Hamiltonian cycles = spanning polygons?

(By "spanning polytope" I mean a spanning subgraph that is the 1-skeleton of a polytope of arbitrary dimension.)

There are connected graphs without spanning polytopes (trees obviously), but there are non-Hamiltonian graphs that have a spanning polytope of dimension d>2, e.g. the Herschel graph.

A google search for "spanning polytope" yields only unrelated results, so my question is:

Is there research on this or a related topic, only under another name?

If not so, does this have an obvious - or not so obvious - reason?