English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The aim of this paper is to extend and generalise some work of Katona on theexistence of perfect matchings or Hamilton cycles in graphs subject to certainconstraints. The most general form of these constraints is that we are given afamily of sets of edges of our graph and are not allowed to use all the edgesof any member of this family. We consider two natural ways of expressingconstraints of this kind using graphs and using set systems.  For the first version we ask for conditions on regular bipartite graphs $G$and $H$ for there to exist a perfect matching in $G$, no two edges of whichform a $4$-cycle with two edges of $H$.  In the second, we ask for conditions under which a Hamilton cycle in thecomplete graph (or equivalently a cyclic permutation) exists, with the propertythat it has no collection of intervals of prescribed lengths whose union is anelement of a given family of sets. For instance we prove that the smallestfamily of $4$-sets with the property that every cyclic permutation of an$n$-set contains two adjacent pairs of points has size between $(1/9+o(1))n^2$and $(1/2-o(1))n^2$. We also give bounds on the general version of this problemand on other natural special cases.  We finish by raising numerous open problems and directions for further study.

Matchings and Hamilton Cycles with Constraints on Sets of Edges