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

DOI10.1007/S00454-019-00155-1zbMATH Open1458.05132arXiv1806.02178OpenAlexW4205469812WikidataQ126665943 ScholiaQ126665943MaRDI QIDQ2225656FDOQ2225656

Authors: Chaya Keller, Micha A. Perles 

Publication date: 10 February 2021

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1806.02178

Recommendations

• Blockers for simple Hamiltonian paths in convex geometric graphs of even order
• Characterization of co-blockers for simple perfect matchings in a convex geometric graph
• Blockers for Noncrossing Spanning Trees in Complete Geometric Graphs
• On the smallest sets blocking simple perfect matchings in a convex geometric graph
• Blockers for triangulations of a convex polygon and a geometric maker-breaker game

zbMATH Keywords

blockergeometric graphcaterpillarsimple Hamiltonian path

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Eulerian and Hamiltonian graphs (05C45)

Cites Work

• The number of caterpillars
• On the smallest sets blocking simple perfect matchings in a convex geometric graph
• A Turán-type theorem on chords of a convex polygon
• Title not available (Why is that?)
• Extremal theory for convex matchings in convex geometric graphs
• Title not available (Why is that?)
• Blockers for simple Hamiltonian paths in convex geometric graphs of even order

Cited In (3)

• On the smallest sets blocking simple perfect matchings in a convex geometric graph
• Blockers for simple Hamiltonian paths in convex geometric graphs of even order
• Blockers for Noncrossing Spanning Trees in Complete Geometric Graphs

This page was built for publication: Blockers for simple Hamiltonian paths in convex geometric graphs of odd order

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2225656)