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

DOI10.1007/S00454-017-9921-8zbMATH Open1392.05065arXiv1607.01034OpenAlexW2963255978MaRDI QIDQ724939FDOQ724939

Chaya Keller, Micha A. Perles

Publication date: 26 July 2018

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

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].

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

Recommendations

• Blockers for simple Hamiltonian paths in convex geometric graphs of odd order
• scientific article
• 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

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)

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?)

Cited In (6)

• Using edge contractions to reduce the semitotal domination number
• Title not available (Why is that?)
• Blockers for simple Hamiltonian paths in convex geometric graphs of odd order
• Blockers for Noncrossing Spanning Trees in Complete Geometric Graphs
• The complexity of blocking (semi)total dominating sets with edge contractions
• Blockers for triangulations of a convex polygon and a geometric maker-breaker game

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)