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.
The Electronic Journal of Combinatorics
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...
Bilangan Terhubung Titik Pelangi pada Graf Garis dan Graf Tengah dari Hasil Operasi Comb Graf Bintang C<sub>3</sub> dan Graf Bintang S<sub>n</sub>
Bilangan Terhubung Titik Pelangi pada Graf Garis dan Graf Tengah dari Hasil Operasi Comb Graf Bintang C<sub>3</sub> dan Graf Bintang S<sub>n</sub>
Penelitian ini bertujuan menentukan bilangan terhubung titik pelangi (rainbow vertex connection number) pada graf garis dan graf tengah yang diperoleh dari hasil operasi comb antar...
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...

