pith. sign in

arxiv: 2509.22571 · v1 · submitted 2025-09-26 · 🧮 math.CO

Visibility Polynomial of Some Graph Classes

Tonny K B , Shikhi M This is my paper

Pith reviewed 2026-05-18 11:51 UTC · model grok-4.3

classification 🧮 math.CO
keywords visibility polynomialmutual visibilitygraph classespathscyclescomplete graphscombinatorial invariants
0
0 comments X

The pith

The visibility polynomials of paths, cycles, complete graphs and other basic classes admit explicit closed-form expressions obtained by characterizing their mutual-visibility sets.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper determines exactly which subsets of vertices qualify as mutual-visibility sets—subsets in which every pair is joined by a shortest path whose internal vertices lie outside the subset—for several standard graph families. These structural descriptions are then converted into simple algebraic formulas that count the number of such sets of each possible cardinality. The resulting polynomials replace the general O(n^3 2^n) enumeration procedure with direct evaluation for the graphs considered. A reader who needs to analyze visibility properties in networks would therefore gain immediate access to the counts instead of running expensive subset searches on each instance.

Core claim

By determining the precise structure of mutual-visibility sets in paths, cycles, complete graphs and related fundamental classes, the authors obtain closed-form expressions for the visibility polynomials of these graphs.

What carries the argument

The visibility polynomial, the generating function that sums x raised to the size of each mutual-visibility set; the complete structural characterizations of which subsets satisfy the mutual-visibility condition supply the explicit coefficients.

If this is right

  • The polynomial for any graph in these families can be evaluated in time linear in the number of vertices.
  • The degree of the polynomial equals the size of a maximum mutual-visibility set in each class.
  • The coefficients give the exact distribution of mutual-visibility set sizes, enabling direct comparison between different families.
  • Surveillance or coordination problems restricted to these graphs can use the formulas to count feasible placements without search.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same case-by-case approach could be applied to trees or grids to produce further closed forms.
  • Network designers might optimize edge additions so that the resulting polynomial satisfies a target distribution of visibility-set sizes.
  • The formulas supply a baseline against which visibility properties of random or constructed graphs can be measured.

Load-bearing premise

The mutual-visibility sets on the chosen graph classes have a sufficiently regular structure that they can be described completely by a small number of cases or parameters rather than by checking every possible subset.

What would settle it

For a path on 15 vertices, compute the number of mutual-visibility sets of each size both by brute-force enumeration of all 2^15 subsets and by the claimed closed-form polynomial; any mismatch in the counts shows the characterization is incomplete.

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript characterizes the mutual-visibility sets for paths, cycles, complete graphs, and certain trees, then derives closed-form expressions for the associated visibility polynomials via direct combinatorial counting from those structural descriptions.

Significance. The explicit closed forms are useful because the general visibility polynomial is known to require exponential time in the worst case. Concrete formulas for these fundamental families supply benchmarks, allow immediate computation for any order, and clarify which structural features of the graphs control the visibility counts. The approach avoids enumeration and relies on case-by-case but exhaustive structural classification.

minor comments (3)
  1. [§2] §2: the definition of a mutual-visibility set is given, but the subsequent counting arguments for cycles would be easier to follow if the authors first stated the precise condition under which two vertices on C_n are mutually visible (i.e., the two arc lengths between them).
  2. [Theorem 4.3] Theorem 4.3 (trees): the closed-form expression is stated only for a specific subclass of trees; a short remark clarifying whether the same formula extends to all trees or requires additional case distinctions would prevent misreading.
  3. [Table 1] Table 1: the column headings for the visibility polynomials of P_n and C_n are not aligned with the row labels; a small formatting adjustment would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary and significance assessment of our manuscript on visibility polynomials for fundamental graph classes. We appreciate the recommendation for minor revision.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper provides explicit structural characterizations of mutual-visibility sets for fundamental graph classes (paths, cycles, complete graphs, trees) and derives closed-form visibility polynomials directly via combinatorial counting arguments on those sets. No step reduces a claimed result to a fitted parameter, self-definition, or load-bearing self-citation by construction; the characterizations are presented as independent inputs that enable the polynomial expressions without circular reduction. The derivation remains self-contained against external graph-theoretic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The abstract introduces no free parameters, no additional axioms beyond standard graph theory, and no invented entities; all contributions are characterizations of existing visibility relations on standard graph families.

pith-pipeline@v0.9.0 · 5636 in / 1000 out tokens · 45068 ms · 2026-05-18T11:51:12.979290+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages · 1 internal anchor

  1. [1]

    Visibility polynomials, dual visibility spectrum, and characterization of total mutual-visibility sets.arXiv preprint, 2024

    Csilla Bujt´ as, Sandi Klavˇ zar, and Jing Tian. Visibility polynomials, dual visibility spectrum, and characterization of total mutual-visibility sets.arXiv preprint, 2024. doi:10.48550/arXiv.2412.03066

    work page doi:10.48550/arxiv.2412.03066 2024

  2. [2]

    Cicerone, G

    S. Cicerone, G. Di Stefano, L. Droˇ z¯dek, J. Hedˇ zet, S. Klavˇ zar, and I.G. Yero. Variety of mutual-visibility problems in graphs.Theoretical Computer Science, 974:114096, 2023.doi:10.1016/j.tcs.2023.114096

    work page doi:10.1016/j.tcs.2023.114096 2023

  3. [3]

    Cicerone, G

    S. Cicerone, G. Di Stefano, and S. Klavˇ zar. On the mutual-visibility in cartesian prod- ucts and in triangle-free graphs.Applied Mathematics and Computation, 438:127619, 2023.doi:10.1016/j.amc.2022.127619

    work page doi:10.1016/j.amc.2022.127619 2023

  4. [4]

    Cicerone, G

    S. Cicerone, G. Di Stefano, S. Klavˇ zar, and I.G. Yero. Mutual-visibility problems on graphs of diameter two.European Journal of Combinatorics, 120:103995, 2024. doi:10.1016/j.ejc.2024.103995

    work page doi:10.1016/j.ejc.2024.103995 2024

  5. [5]

    Addison-Wesley Series in Mathematics

    Frank Harary.Graph Theory. Addison-Wesley Series in Mathematics. Addison- Wesley, Reading, MA, 1969

    work page 1969

  6. [6]

    Klavˇ zar, G

    S. Irˇ siˇ c, S. Klavˇ zar, G. Rus, and J. Tuite. General position polynomials.Results in Mathematics, 79, 2024.doi:10.1007/s00025-024-02133-3

    work page doi:10.1007/s00025-024-02133-3 2024

  7. [7]

    Korˇ ze and A

    D. Korˇ ze and A. Vesel. Variety of mutual-visibility problems in hypercubes.Ap- plied Mathematics and Computation, 491:129218, 2025.doi:10.1016/j.amc.2024. 129218. 8 TONNY K B AND SHIKHI M

    work page doi:10.1016/j.amc.2024 2025

  8. [8]

    Manuel and S

    P. Manuel and S. Klavˇ zar. A general position problem in graph theory.Bul- letin of the Australian Mathematical Society, 98:177–187, 2018.doi:10.1017/ S0004972718000473

    work page 2018

  9. [9]

    A Rosenfeld and A. Y. Wu. Geodesic convexity in discrete spaces.Journal of Infor- mation Sciences, 80:127–132, 1994

    work page 1994

  10. [10]

    419, 126850 (2022)

    Gabriele Di Stefano. Mutual visibility in graphs.Applied Mathematics and Compu- tation, 419, 2022.doi:10.1016/j.amc.2021.126850

    work page doi:10.1016/j.amc.2021.126850 2022

  11. [11]

    On the Visibility Polynomial of Graphs

    K. B Tonny and M. Shikhi. On the visibility polynomial of graphs, 2025. arXiv:2507.01851 [math.CO].doi:10.48550/arXiv.2507.01851

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2507.01851 2025

  12. [12]

    B Tonny and M

    K. B Tonny and M. Shikhi. Visibility polynomial of corona of two graphs, 2025. arXiv.doi:10.48550/arXiv.2509.02509

    work page doi:10.48550/arxiv.2509.02509 2025

  13. [13]

    S. V. Ullas Chandran and G.J. Parthasarathy. The geodesic irredundant sets in graphs.International Journal of Mathematical Combinatorics, 4:135–143, 2016. Tonny K B, Department of Mathematics, College of Engineering Trivandrum, Thiru- vananthapuram, Kerala, India, 695016. Email address:tonnykbd@cet.ac.in Shikhi M, Department of Mathematics, College of Eng...

    work page 2016