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

DOI10.1007/S00454-017-9921-8MaRDI QIDQ724939zbMATHOpenAlexFDO

Authors Chaya Keller, Micha A. Perles

Publication date 26 July 2018

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

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

zbMATH Keywords

blockergeometric graphcaterpillarsimple Hamiltonian path

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Eulerian and Hamiltonian graphs (05C45) Distance in graphs (05C12) Enumeration in graph theory (05C30) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: Let G be a complete convex geometric graph on 2m vertices, and let F be a family of subgraphs of G. A blocker for F is a set of edges, of smallest possible size, that meets every element of F. In [C. Keller and M. A. Perles, On the smallest sets blocking simple perfect matchings in a convex geometric graph, Israel J. Math. 187 (2012), pp. 465-484], we gave an explicit description of all blockers for the family of simple perfect matchings (SPMs) of G. In this paper we show that the family of simple Hamiltonian paths (SHPs) in G has exactly the same blockers as the family of SPMs. Our argument is rather short, and provides a much simpler proof of the result of [KP12].

Recommendations

• Blockers for simple Hamiltonian paths in convex geometric graphs of odd order
• scientific article; zbMATH DE number 4160773
• Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices
• On Hamiltonian colorings of block graphs
• Blockers for Noncrossing Spanning Trees in Complete Geometric Graphs
• Hamilton cycles in restricted block-intersection graphs
• Characterization of co-blockers for simple perfect matchings in a convex geometric graph
• Hamiltonian chromatic number of block graphs
• Revisiting the Hamiltonian theme in the square of a block: the case of \(DT\)-graphs
• On the smallest sets blocking simple perfect matchings in a convex geometric graph

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
• 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

(8)

• Blockers for simple Hamiltonian paths in convex geometric graphs of odd order
• 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
• scientific article; zbMATH DE number 5060433 (Why is no real title available?)
• On the smallest sets blocking simple perfect matchings in a convex geometric graph
• Using edge contractions to reduce the semitotal domination number
• The complexity of blocking (semi)total dominating sets with edge contractions

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

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