Search engine for discovering works of Art, research articles, and books related to Art and Culture
ShareThis
Javascript must be enabled to continue!

Disjoint Compatibility Graph of Non-Crossing Matchings of Points in Convex Position

View through CrossRef
Let $X_{2k}$ be a set of $2k$ labeled points in convex position in the plane. We consider geometric non-intersecting straight-line perfect matchings of $X_{2k}$. Two such matchings, $M$ and $M'$, are disjoint compatible if they do not have common edges, and no edge of $M$ crosses an edge of $M'$. Denote by $\rm{DCM}_k$ the graph whose vertices correspond to such matchings, and two vertices are adjacent if and only if the corresponding matchings are disjoint compatible. We show that for each $k \geq 9$, the connected components of $\rm{DCM}_k$ form exactly three isomorphism classes - namely, there is a certain number of isomorphic small components, a certain number of isomorphic medium components, and one big component. The number and the structure of small and medium components is determined precisely.
Title: Disjoint Compatibility Graph of Non-Crossing Matchings of Points in Convex Position
Description:
Let $X_{2k}$ be a set of $2k$ labeled points in convex position in the plane.
We consider geometric non-intersecting straight-line perfect matchings of $X_{2k}$.
Two such matchings, $M$ and $M'$, are disjoint compatible if they do not have common edges, and no edge of $M$ crosses an edge of $M'$.
Denote by $\rm{DCM}_k$ the graph whose vertices correspond to such matchings, and two vertices are adjacent if and only if the corresponding matchings are disjoint compatible.
We show that for each $k \geq 9$, the connected components of $\rm{DCM}_k$ form exactly three isomorphism classes - namely, there is a certain number of isomorphic small components, a certain number of isomorphic medium components, and one big component.
The number and the structure of small and medium components is determined precisely.

Related Results

Ostrowski-Type Fractional Integral Inequalities: A Survey
Ostrowski-Type Fractional Integral Inequalities: A Survey
This paper presents an extensive review of some recent results on fractional Ostrowski-type inequalities associated with a variety of convexities and different kinds of fractional ...
Graph convolutional neural networks for 3D data analysis
Graph convolutional neural networks for 3D data analysis
(English) Deep Learning allows the extraction of complex features directly from raw input data, eliminating the need for hand-crafted features from the classical Machine Learning p...
Disjoint Dunford–Pettis-Type Properties in Banach Lattices
Disjoint Dunford–Pettis-Type Properties in Banach Lattices
ABSTRACT New characterizations of the disjoint Dunford–Pettis property of order p (disjoint DPPp) are proved and applied to show that a Banach lattice of cotype p ha...
Convex hull peeling
Convex hull peeling
Enveloppes convexes pelées Cette thèse porte sur la construction du convex hull peeling (qu’on pourrait traduire littéralement par enveloppe convexe pelée). Le conv...
A tight Erdős-Pósa function for planar minors
A tight Erdős-Pósa function for planar minors
Let F be a family of graphs. Then for every graph G the maximum number of disjoint subgraphs of G, each isomorphic to a member of F, is at most the minimum size of a set of vertice...
Bootstrapping a Biodiversity Knowledge Graph
Bootstrapping a Biodiversity Knowledge Graph
The "biodiversity knowledge graph" is a nice metaphor for connecting biodiversity data sources, but can we actually build it? Do we have sufficient linked data available? Given tha...

Back to Top