5
$\begingroup$

Let $G$ be a $k$-connected planar triangulation ($k\geq 4$) and let $C$ be a Hamilton cycle of $G$. Then:

  1. Which conditions would be sufficient to assure that every triangle of $G$ has at least one edge belonging to the set of edges induced by $C$?

  2. Or, does there exist at least one Hamilton cycle for every 4-connected planar triangulation or every 5-connected planar triangulation with property in (1)?

For example: In picture below, not every triangle of $G$ has at least one edge belonging to the set of edges induced by the hamilton cycle $C_1$ (in red+blue)

Picture 1

However, in the next Figure, all triangles contains an edge belonging to the Hamilton cycle $C_2$ (in red):

Picture 2

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ By "a Hamiltonian cycle without such a property", do you mean the property in 1, and is that cycle contained in p. 12 of the linked slides? (Maybe that's not even a grammatically correct guess ….) If not, then which page is it? If so, then would you be willing to add, or would you mind my adding, an image of the relevant example, since slides on the web are not always long lived? \\ Also, please do not use $math\ mode$ for emphasis. I think there is no good way to do emphasis in the title. $\endgroup$
    – LSpice
    Commented Jul 28, 2023 at 20:49
  • 1
    $\begingroup$ Re, thanks for your edit, I guess in response to my comment! I think I was unclear, and I apologise: it is fine and appropriate to use math mode for math, like $C$ and $G$; it is just inappropriate to use it for text, like ‘$s.t.$’. Nonetheless, it is also fine and appropriate not to use math mode for math in the title, as long as it's consistent, so please feel free to leave it however you like. $\endgroup$
    – LSpice
    Commented Jul 28, 2023 at 22:44

1 Answer 1

Reset to default
3
$\begingroup$

Gunnar Brinkmann informs me that this paper constructs planar triangulations where every hamiltonian cycle misses all the edges of many triangles. Some of the examples are even 5-connected.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks, strong result. Exactly what I needed to discard this hypothesis. $\endgroup$
    – Jose Antonio Martin H
    Commented Jul 29, 2023 at 9:12
  • $\begingroup$ Hi, can the results of that paper be extended to more general class of planar graphs? Say 4 regular? $\endgroup$
    – Jose Antonio Martin H
    Commented Aug 4, 2023 at 22:50
  • $\begingroup$ @JoseAntonioMartinH You should ask Gunnar. His email is easy to find. $\endgroup$
    – Brendan McKay
    Commented Aug 5, 2023 at 2:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .