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

dmtcs:6678 - Discrete Mathematics & Theoretical Computer Science, May 6, 2022, vol. 24, no. 1 - https://doi.org/10.46298/dmtcs.6678
On the connectivity of the disjointness graph of segments of point sets in general position in the plane

Authors: 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$.


    Volume: vol. 24, no. 1
    Section: Combinatorics
    Published on: May 6, 2022
    Accepted on: April 7, 2022
    Submitted on: July 31, 2020
    Keywords: Mathematics - Combinatorics,05C40

    Share

    Consultation statistics

    This page has been seen 521 times.
    This article's PDF has been downloaded 494 times.