Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2506.00689 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912410734952448 |
|---|---|
| author | Leaños, J. Lomelí-Haro, M. Ndjatchi, Christophe Ríos-Castro, L. M. |
| author_facet | Leaños, J. Lomelí-Haro, M. Ndjatchi, Christophe Ríos-Castro, L. M. |
| contents | Let $G=(V(G),E(G))$ be a simple graph, and let $U\subseteq V(G)$. Two distinct vertices $x,y\in U$ are $U$-mutually visible if $G$ contains a shortest $x$-$y$ path that is internally disjoint from $U$. $U$ is called a mutual-visibility set of $G$ if any two vertices of $U$ are $U$-mutually visible. The mutual-visibility number $μ(G)$ of $G$ is the size of a largest mutual-visibility set of $G$. Let $P$ be a set of $n\geq 3$ points in ${\mathbb R}^2$ in general position. The disjointness graph of segments $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. In this paper we establish tight lower and upper bounds for $μ(D(P))$, and show that almost all edge disjointness graphs have diameter 2. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_00689 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Mutual-visibility of the disjointness graph of segments in ${\mathbb R}^2$ Leaños, J. Lomelí-Haro, M. Ndjatchi, Christophe Ríos-Castro, L. M. Combinatorics Let $G=(V(G),E(G))$ be a simple graph, and let $U\subseteq V(G)$. Two distinct vertices $x,y\in U$ are $U$-mutually visible if $G$ contains a shortest $x$-$y$ path that is internally disjoint from $U$. $U$ is called a mutual-visibility set of $G$ if any two vertices of $U$ are $U$-mutually visible. The mutual-visibility number $μ(G)$ of $G$ is the size of a largest mutual-visibility set of $G$. Let $P$ be a set of $n\geq 3$ points in ${\mathbb R}^2$ in general position. The disjointness graph of segments $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. In this paper we establish tight lower and upper bounds for $μ(D(P))$, and show that almost all edge disjointness graphs have diameter 2. |
| title | Mutual-visibility of the disjointness graph of segments in ${\mathbb R}^2$ |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2506.00689 |