Visibility polynomials, dual visibility spectrum, and characterization of total mutual-visibility sets
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917133207732224 |
|---|---|
| author | Bujtás, Csilla Klavžar, Sandi Tian, Jing |
| author_facet | Bujtás, Csilla Klavžar, Sandi Tian, Jing |
| contents | Mutual-visibility sets were motivated by visibility in distributed systems and social networks, and intertwine with several classical mathematical areas. Monotone properties of the variety of mutual-visibility sets, and restrictions of such sets to convex and isometric subgraphs are studied. Dual mutual-visibility sets are shown to be intrinsically different from other types of mutual-visibility sets. It is proved that for every finite subset $Z$ of positive integers there exists a graph $G$ that has a dual mutual-visibility set of size $i$ if and only if $i\in Z\cup \{0\}$, while for the other types of mutual-visibility such a set consists of consecutive integers. Visibility polynomials are introduced and their properties derived. As a surprise, every polynomial with nonnegative integer coefficients and with a constant term $1$ is a dual visibility polynomial of some graph. Characterizations are given for total mutual-visibility sets, for graphs with total mutual-visibility number $1$, and for sets which are not total mutual-visibility sets, yet every proper subset is such. Along the way an earlier result from the literature is corrected. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_03066 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Visibility polynomials, dual visibility spectrum, and characterization of total mutual-visibility sets Bujtás, Csilla Klavžar, Sandi Tian, Jing Combinatorics Mutual-visibility sets were motivated by visibility in distributed systems and social networks, and intertwine with several classical mathematical areas. Monotone properties of the variety of mutual-visibility sets, and restrictions of such sets to convex and isometric subgraphs are studied. Dual mutual-visibility sets are shown to be intrinsically different from other types of mutual-visibility sets. It is proved that for every finite subset $Z$ of positive integers there exists a graph $G$ that has a dual mutual-visibility set of size $i$ if and only if $i\in Z\cup \{0\}$, while for the other types of mutual-visibility such a set consists of consecutive integers. Visibility polynomials are introduced and their properties derived. As a surprise, every polynomial with nonnegative integer coefficients and with a constant term $1$ is a dual visibility polynomial of some graph. Characterizations are given for total mutual-visibility sets, for graphs with total mutual-visibility number $1$, and for sets which are not total mutual-visibility sets, yet every proper subset is such. Along the way an earlier result from the literature is corrected. |
| title | Visibility polynomials, dual visibility spectrum, and characterization of total mutual-visibility sets |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2412.03066 |