J. Leaños ; Christophe Ndjatchi ; L. M. Ríos-Castro
-
On the connectivity of the disjointness graph of segments of point sets
in general position in the plane
On the connectivity of the disjointness graph of segments of point sets
in general position in the planeArticle
Authors: J. Leaños ; Christophe Ndjatchi ; L. M. Ríos-Castro
NULL##0000-0003-2702-9981##NULL
J. Leaños;Christophe Ndjatchi;L. M. Ríos-Castro
Let $P$ be a set of $n\geq 3$ points in general position in the plane. The
edge disjointness graph $D(P)$ of $P$ is the graph whose vertices are all the
closed straight line segments with endpoints in $P$, two of which are adjacent
in $D(P)$ if and only if they are disjoint. We show that the connectivity of
$D(P)$ is at least
$\binom{\lfloor\frac{n-2}{2}\rfloor}{2}+\binom{\lceil\frac{n-2}{2}\rceil}{2}$,
and that this bound is tight for each $n\geq 3$.