pith. sign in

arxiv: 1806.02178 · v1 · pith:UCAR2OJSnew · submitted 2018-06-06 · 🧮 math.CO

Blockers for simple Hamiltonian paths in convex geometric graphs of odd order

classification 🧮 math.CO
keywords blockerssimplecaseconvexfamilygeometrichamiltonianpaths
0
0 comments X
read the original abstract

Let G be a complete convex geometric graph, and let F be a family of subgraphs of G. A blocker for F is a set of edges, of smallest possible size, that has an edge in common with every element of F. In [C. Keller and M. A. Perles, Blockers for simple Hamiltonian paths in convex geometric graphs of even order, Disc. Comput. Geom., 60(1) (2018), pp. 1-8] we gave an explicit description of all blockers for the family of simple (i.e., non-crossing) Hamiltonian paths (SHPs) in G in the `even' case |V(G)|=2m. It turned out that all the blockers are simple caterpillar trees of a certain class. In this paper we give an explicit description of all blockers for the family of SHPs in the `odd' case |V(G)|=2m-1. In this case, the structure of the blockers is more complex, and in particular, they are not necessarily simple. Correspondingly, the proof is more complicated.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.