Visibility Polynomial of Some Graph Classes
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917393462198272 |
|---|---|
| author | B, Tonny K M, Shikhi |
| author_facet | B, Tonny K M, Shikhi |
| contents | Mutual visibility in graphs provides a framework for analysing how vertices can observe one another along shortest paths free of internal obstructions. The visibility polynomial, which enumerates mutual-visibility sets of all orders, has emerged as a central invariant in this study, with both theoretical significance and practical relevance in areas such as surveillance, target tracking, and distributed coordination. While computing this polynomial is computationally demanding, with known complexity $O(n^32^n)$, explicit characterizations for specific graph families yield valuable structural insights. In this paper, we characterize the mutual-visibility sets of several fundamental graph classes and derive closed-form expressions for their associated visibility polynomials. These results deepen the understanding of visibility-based invariants and expand the toolkit available for studying visibility phenomena in networks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_22571 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Visibility Polynomial of Some Graph Classes B, Tonny K M, Shikhi Combinatorics 05C30, 05C31, 05C76 Mutual visibility in graphs provides a framework for analysing how vertices can observe one another along shortest paths free of internal obstructions. The visibility polynomial, which enumerates mutual-visibility sets of all orders, has emerged as a central invariant in this study, with both theoretical significance and practical relevance in areas such as surveillance, target tracking, and distributed coordination. While computing this polynomial is computationally demanding, with known complexity $O(n^32^n)$, explicit characterizations for specific graph families yield valuable structural insights. In this paper, we characterize the mutual-visibility sets of several fundamental graph classes and derive closed-form expressions for their associated visibility polynomials. These results deepen the understanding of visibility-based invariants and expand the toolkit available for studying visibility phenomena in networks. |
| title | Visibility Polynomial of Some Graph Classes |
| topic | Combinatorics 05C30, 05C31, 05C76 |
| url | https://arxiv.org/abs/2509.22571 |