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

DOI10.1007/S00454-019-00155-1MaRDI QIDQ2225656zbMATHOpenAlexWikidataFDO

Authors Chaya Keller, Micha A. Perles

Publication date 10 February 2021

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

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

zbMATH Keywords

blockergeometric graphcaterpillarsimple Hamiltonian path

Mathematics Subject Classification ID

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

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.

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

Cites work

• scientific article; zbMATH DE number 3643294 (Why is no real title available?)
• scientific article; zbMATH DE number 2209719 (Why is no real title available?)
• A Turán-type theorem on chords of a convex polygon
• Blockers for simple Hamiltonian paths in convex geometric graphs of even order
• Extremal theory for convex matchings in convex geometric graphs
• On the smallest sets blocking simple perfect matchings in a convex geometric graph
• The number of caterpillars

Cited in

(5)

• Blockers for triangulations of a convex polygon and a geometric maker-breaker game
• 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 simple Hamiltonian paths in convex geometric graphs of even order

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)