Name
Abstract | ||
|---|---|---|
Let G be a complete convex geometric graph, and let F be a family of subgraphs of G. A blocker for Fis a set of edges, of smallest possible size, that has an edge in common with every element of F. In Keller and Perles (Discrete Comput Geom 60(1):1-8, 2018) 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. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1007/s00454-019-00155-1 | DISCRETE & COMPUTATIONAL GEOMETRY |
DocType | Volume | Issue |
Journal | 65 | 2 |
ISSN | Citations | PageRank |
0179-5376 | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chaya Keller | 1 | 3 | 4.52 |
| Micha A. Perles | 2 | 38 | 10.65 |