Geodesic
On the connectivity of the disjointness graph of segments of point sets in general position in the plane
Discrete mathematics & theoretical computer science, Tome 24 (2022) no. 1.

Voir la notice de l'article provenant de la source Episciences

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$.
DOI : 10.46298/dmtcs.6678
Classification : 05C40, 52C35 
@article{DMTCS_2022_24_1_a13,
     author = {Lea\~nos, J. and Ndjatchi, Christophe and R{\'\i}os-Castro, L. M.},
     title = {On the connectivity of the disjointness graph of segments of point sets in general position in the plane},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {24},
     number = {1},
     year = {2022},
     doi = {10.46298/dmtcs.6678},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6678/}
}
TY  - JOUR
AU  - Leaños, J.
AU  - Ndjatchi, Christophe
AU  - Ríos-Castro, L. M.
TI  - On the connectivity of the disjointness graph of segments of point sets in general position in the plane
JO  - Discrete mathematics & theoretical computer science
PY  - 2022
VL  - 24
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6678/
DO  - 10.46298/dmtcs.6678
LA  - en
ID  - DMTCS_2022_24_1_a13
ER  - 
%0 Journal Article
%A Leaños, J.
%A Ndjatchi, Christophe
%A Ríos-Castro, L. M.
%T On the connectivity of the disjointness graph of segments of point sets in general position in the plane
%J Discrete mathematics & theoretical computer science
%D 2022
%V 24
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6678/
%R 10.46298/dmtcs.6678
%G en
%F DMTCS_2022_24_1_a13
Leaños, J.; Ndjatchi, Christophe; Ríos-Castro, L. M. On the connectivity of the disjointness graph of segments of point sets in general position in the plane. Discrete mathematics & theoretical computer science, Tome 24 (2022) no. 1. doi : 10.46298/dmtcs.6678. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6678/

Cité par Sources :