2
$\begingroup$

Given a maximal planar graph (+6vertices) without separating triangles. Then it can have many Hamilton cycles°. Such a cycle divides the graph into two triangulated polygons. Is it always possible to choose a hamiltonian cycle so that at least one of the polygons has only two ears?°° In fact, in most of the cases I investigated, it was possible to choose a hamiltonian cycle so that both polygons had no more than two ears, e.g. the Heawood graph on 25 vertices. With three or more degree 3 vertices in the maximal planar graph it's sometimes impossible for both polygons having no more than 2 ears.

(°) A Hamilton cycle visits each vertex once and returns in the startvertex. (°°) An ear of a triangulated polygon is a triangle with 2 of it's edges on the boundary.

Nine maximal planar graphs with hamilton cycle

Improve this question
$\endgroup$
3
  • $\begingroup$ Your use of "possible" and "impossible" is confusing, and "one" is also unclear. Does your bold sentence mean "Is it always possible to choose a hamiltonian cycle so that at least one of the polygons has only two ears?" (After noting that less than two ears never happens; this is equivalent to a non-trivial tree having at least two leaves.) $\endgroup$
    – Brendan McKay
    Commented Mar 4, 2023 at 1:06
  • $\begingroup$ @Brendan: Yes, the bold sentence is the question. And in fact I'm only interrested in it for maximal planar polygons without separating triangles. What follows (included the drawings) is peripheral information, not essential for it. And of coarse a trangulated planar polygon has at least two ears (Gary Meister, 1975 and Max Dehn circa 1899, Wikipedia). $\endgroup$
    – P.Labarque
    Commented Mar 4, 2023 at 10:12
  • $\begingroup$ @Brendan: Now I understand the confusion. Your question is what I mean. It's corrected. Excuses. $\endgroup$
    – P.Labarque
    Commented Mar 4, 2023 at 17:14

1 Answer 1

Reset to default
1
$\begingroup$

Carol Zamfirescu and Gunnar Brinkmann have informed me that this paper answers the question.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, Brendan, Gunnar and Carol. For me it's the best answer up to now, although!. Is it also valuable for more than 130 triangles? Is it also valuable for more than 21 vertices without separating triangles (degree 4 or 5 graphs)? $\endgroup$
    – P.Labarque
    Commented Mar 5, 2023 at 12:13

You must log in to answer this question.

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