pith. sign in

arxiv: 2507.01851 · v2 · submitted 2025-07-02 · 🧮 math.CO

On the Visibility Polynomial of Graphs

Tonny K B , Shikhi M This is my paper

Pith reviewed 2026-05-19 06:20 UTC · model grok-4.3

classification 🧮 math.CO
keywords visibility polynomialmutual-visibility setscycle graphsgraph joinsgraph polynomialscombinatorial enumeration
0
0 comments X

The pith

The visibility polynomial counts mutual-visibility sets in a graph, where each pair in the set has a shortest path avoiding the set internally, and it is computed explicitly for cycles and joins.

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

The paper defines a mutual-visibility set X in a graph G as a subset where every pair of vertices in X is X-visible, meaning a shortest path between them has no internal vertices from X. It introduces the visibility polynomial as the generating function summing the counts of these sets by cardinality. For cycle graphs, the work identifies the specific instance at which the number of maximal mutual-visibility sets becomes equal. It also derives the form of the visibility polynomial when two graphs are combined via the join operation.

Core claim

The visibility polynomial nu(G) equals the sum of r_i x^i, where r_i is the number of mutual-visibility sets of size i. For cycle graphs, the instance is identified at which the number of maximal mutual-visibility sets is equal. The polynomial of the join of two graphs is studied, and an algorithm to compute the polynomial for any graph runs in O(n^3 2^n) time.

What carries the argument

The mutual-visibility set: a vertex subset X such that every pair in X admits a shortest connecting path whose internal vertices lie outside X.

If this is right

  • The visibility polynomial takes an explicit form for every cycle graph.
  • The visibility polynomial of a join G join H can be expressed in terms of the polynomials or properties of G and H.
  • Enumerating mutual-visibility sets is feasible only for graphs with small numbers of vertices given the exponential term in the runtime.

Where Pith is reading between the lines

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

  • The polynomial supplies a new numerical invariant that may separate non-isomorphic graphs even when other standard invariants coincide.
  • The same visibility relation could be applied to directed graphs or to weighted graphs to produce analogous polynomials.
  • Practical computation for larger instances would require dynamic programming or symmetry reduction to mitigate the 2^n factor.

Load-bearing premise

The definition of X-visible, as the existence of a shortest u-v path whose internal vertices avoid X, correctly captures the mutual-visibility relation.

What would settle it

Compute the actual numbers of maximal mutual-visibility sets for two cycle graphs of different lengths and check whether they match at the instance claimed to be equal.

Figures

Figures reproduced from arXiv: 2507.01851 by Shikhi M, Tonny K B.

Figure 1
Figure 1. Figure 1: Non-isomorphic graphs with the same visibility polynomial Using a Python program and high performance computing facilities, we identified all non-isomorphic graphs of order up to 9 that have identical visibility polynomials. In [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The graphs G and H Here m = 4 and n = 6, and the visibility polynomial of the join of G and H is V(G∨H) = P9 i=0 rix i . For 0 ≤ i ≤ 4, the number of mutual-visibility sets of size i is given by ri = [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Mutual-visibility sets in G ∨ H Remark: Since Km,n ∼= Km ∨ Kn, letting G = Km and H = Kn, in Theorem 22, the result of Theorem 14 can be deduced using Vandermonde identity in combinatorics. 6. Time Complexity of Visibility Polynomial Problem Di Stefano [1] proposed an algorithm, referred to as MV , which verifies in polynomial time whether a given subset P of vertices in a graph G(V, E) forms a mutual-visi… view at source ↗
read the original abstract

Let G(V,E) be a simple graph and let X subset of V. Two vertices u and v are said to be X-visible if there exists a shortest u,v-path P such that V(P) intersection X is a subset of {u, v}. A set X is called a mutual-visibility set of G if every pair of vertices in X are X-visible. The visibility polynomial of a graph G is defined as nu (G)=sum_{i >= 0} r_i x^i, where r_i denotes the number of mutual-visibility sets in G of cardinality i. In the present paper, the visibility polynomial is studied for some well-known classes of graphs. In particular, the instance at which the number of maximal mutual-visibility sets is equal for cycle graphs is identified. The visibility polynomial of the join of two graphs is studied. The algorithm for computing the visibility polynomial of a graph has been identified to have a time complexity of O(n^3.2^n) making the problem computationally intensive for larger graphs.

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

1 major / 2 minor

Summary. The paper defines X-visible vertices via shortest paths whose internal vertices avoid X (except endpoints), then mutual-visibility sets as those X where all pairs are X-visible. The visibility polynomial ν(G) = ∑ r_i x^i counts mutual-visibility sets by cardinality. It computes this polynomial explicitly for cycle graphs C_n, identifies the parameter value at which the number of maximal mutual-visibility sets coincides across cycle graphs, derives the form of the visibility polynomial for the join of two graphs, and states an O(n^3 2^n) algorithm for general computation.

Significance. If the explicit computations and the identification for cycles hold, the visibility polynomial supplies a new graph invariant encoding mutual-visibility information, with concrete closed forms or values for standard families (cycles, joins) that can serve as test cases for further theory. The algorithmic complexity bound, once verified, indicates the invariant is computable for moderate n and highlights its practical limits.

major comments (1)
  1. The manuscript asserts an O(n^3 2^n) algorithm for computing the visibility polynomial but supplies neither a description of the algorithm nor a proof sketch of the complexity bound (mentioned in the abstract and presumably in the computational section). This is load-bearing for the claim that the problem is 'computationally intensive for larger graphs.'
minor comments (2)
  1. The abstract and results sections would benefit from one or two small explicit examples (e.g., ν(C_4) or ν(C_5)) to illustrate the definition before stating general claims for cycles.
  2. Notation for the visibility polynomial is introduced as nu(G) in the abstract but should be consistently rendered as ν(G) or a similar symbol throughout the text and any displayed equations.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback on our manuscript. We address the major comment below and will revise the paper accordingly to improve clarity and completeness.

read point-by-point responses

  1. Referee: The manuscript asserts an O(n^3 2^n) algorithm for computing the visibility polynomial but supplies neither a description of the algorithm nor a proof sketch of the complexity bound (mentioned in the abstract and presumably in the computational section). This is load-bearing for the claim that the problem is 'computationally intensive for larger graphs.'

    Authors: We agree that the current manuscript only states the O(n^3 2^n) complexity bound without providing an explicit description of the algorithm or a proof sketch. This omission weakens the supporting claim. In the revised version we will insert a dedicated subsection that fully describes the algorithm (an enumeration over all subsets combined with O(n^3) shortest-path checks per subset to verify the mutual-visibility condition) and supplies a concise proof of the stated time bound. The revision will also clarify why the resulting complexity renders the problem intensive for larger n. revision: yes

Circularity Check

0 steps flagged

No significant circularity; definitions and computations are self-contained

full rationale

The paper begins with explicit definitions of X-visible pairs and mutual-visibility sets, then defines the visibility polynomial directly as the generating function summing the counts r_i of such sets by size. All subsequent results for cycles, joins, and other families follow from direct enumeration under these definitions, with the noted parameter instance for equal maximal counts in cycles arising from explicit computation rather than any fitted input or self-referential prediction. The stated O(n^3 2^n) complexity is a complexity bound on the enumeration algorithm, not a derived claim that reduces to prior outputs. No self-citations, ansatzes, or uniqueness theorems appear as load-bearing steps, rendering the derivation chain independent of its own results.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The work rests on the newly introduced definitions of X-visible and mutual-visibility sets together with standard assumptions about simple undirected graphs and shortest paths.

axioms (1)
  • domain assumption G is a simple undirected graph with no loops or multiple edges.
    Stated at the outset when defining G(V,E) and the visibility relation.
invented entities (1)
  • mutual-visibility set no independent evidence
    purpose: To define subsets X in which every pair is X-visible via shortest paths.
    Newly postulated combinatorial object whose properties are then studied.

pith-pipeline@v0.9.0 · 5697 in / 1248 out tokens · 51948 ms · 2026-05-19T06:20:21.434698+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.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Mutual visibility in Moore graphs and $(d,2)$-graphs with defect

    math.CO 2025-10 unverdicted novelty 6.0

    Mutual-visibility number equals 20 in the Hoffman-Singleton graph; algebraic conditions and exact values are given for small-defect (d,2)-graphs.

  2. Visibility Polynomial of Some Graph Classes

    math.CO 2025-09 unverdicted novelty 5.0

    Derives closed-form visibility polynomials for several graph classes by characterizing their mutual-visibility sets.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages · cited by 2 Pith papers

  1. [1]

    419, 126850 (2022)

    Gabriele Di Stefano, Mutual visibility in graphs , Applied Mathematics and Computation. 419, 126850 (2022). 10.1016/j.amc.2021.126850

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

  2. [2]

    Rosenfeld and A

    A. Rosenfeld and A. Y. Wu. Geodesic convexity in discrete spaces, Journal of Information Sciences, 80(1-2):127–132, 1994

    work page 1994

  3. [3]

    A. Y. Wu and A. Rosenfeld. Geodesic visibility in graphs , Journal of Information Sciences, 108(1-4):5–12, 1998

    work page 1998

  4. [4]

    Cicerone, S., Di Fonso, A., Di Stefano, G., Navarra, A. (2023). Time-Optimal Geodesic Mutual Visibility of Robots on Grids Within Minimum Area . In: Dolev, S., Schieber, B. (eds) Stabilization, Safety, and Security of Distributed Systems. SSS 2023. Lecture Notes in Computer Science, vol 14310. Springer, Cham

    work page 2023

  5. [5]

    Di Luna, P

    G.A. Di Luna, P. Flocchini, S.G. Chaudhuri, F. Poloni, N. Santoro, G. Viglietta, Mutual visibility by luminous robots without collisions, Information and Computation. 254 (2017) 392–418, doi:10.1016/j.ic.2016.09.005

    work page doi:10.1016/j.ic.2016.09.005 2017

  6. [6]

    Subhash Bhagat, PaulomiDey, RajarshiRay, Collision-Free Linear Time Mutual Visibility for Asynchronous Fat Robots , Proceedings of the 25th International Conference on Distributed Computing and Networking, doi:10.1145/3631461.3631544, 2024

    work page doi:10.1145/3631461.3631544 2024

  7. [7]

    Alsaedi, R.J., Gudmundsson, J., van Renssen, A. (2023). The Mutual Visibility Problem for Fat Robots. In: Morin, P., Suri, S. (eds) Algorithms and Data Structures. WADS 2023. Lecture Notes in Computer Science, vol 14079. Springer, Cham. 12 TONNY K B AND SHIKHI M

    work page 2023

  8. [8]

    ICDCN ’23: Proceedings of the 24th International Conference on Distributed Computing and Networking, 150–159 (2023)

    Cicerone, S., Di Fonso, A., Di Stefano, G., Navarra, A.: The geodesic mutual visibility problem for oblivious robots: The case of trees. ICDCN ’23: Proceedings of the 24th International Conference on Distributed Computing and Networking, 150–159 (2023)

    work page 2023

  9. [9]

    G. Sharma, Mutual visibility for robots with lights tolerating light faults, in: 2018 IEEE International Parallel and Distributed Processing Symposium Workshops, IEEE Computer Society, 2018, pp. 829–836, doi:10.1109/IPDPSW.2018.00130

    work page doi:10.1109/ipdpsw.2018.00130 2018

  10. [10]

    Aljohani, P

    A. Aljohani, P. Poudel, G. Sharma, Complete visitability for autonomous robots on graphs, in: IEEE Inter- national Parallel and Distributed Processing Symposium, IPDPS, IEEE Computer Society, 2018, pp. 733–742, doi:10.1109/IPDPS.2018.00083

    work page doi:10.1109/ipdps.2018.00083 2018

  11. [11]

    Manuel, P., Klavˇ zar, S.: A general position problem in graph theory. Bull. Aust. Math. Soc. 98, 177–187 (2018)

    work page 2018

  12. [12]

    Chandran S.V., G.J

    U. Chandran S.V., G.J. Parthasarathy, The geodesic irredundant sets in graphs, Int. J. Math. Combin. 4 (2016) 135–143

    work page 2016

  13. [13]

    Klavˇ zar, G

    Irˇ siˇ c, S. Klavˇ zar, G. Rus, J. Tuite, General position polynomials, Results Math. 79 (2024) Paper 110. doi:10.1007/s00025-024-02133-3

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

  14. [14]

    Results Math

    Korˇ ze, D., Vesel, A.: Mutual-Visibility Sets in Cartesian Products of Paths and Cycles. Results Math. 79, 116 (2024)

    work page 2024

  15. [15]

    Appl Math Comput

    Korˇ ze, D., Vesel, A.: Variety of mutual-visibility problems in hypercubes. Appl Math Comput. 491, 129218 (2025).doi:10.1016/j.amc.2024.129218

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

  16. [16]

    Tian, J., Klavˇ zar, S.: Graphs with total mutual-visibility number zero and total mutual-visibility in Cartesian products. Discuss. Math. Graph Theory 44, 1277–1291 (2024). doi:10.7151/dmgt.2496

    work page doi:10.7151/dmgt.2496 2024

  17. [17]

    Axenovich, D

    M. Axenovich, D. Liu, Visibility in hypercubes, arXiv preprint, doi:10.48550/arXiv.2402.04791 (2024)

    work page doi:10.48550/arxiv.2402.04791 2024

  18. [18]

    Cicerone, A

    S. Cicerone, A. Di Fonso, G. Di Stefano, A. Navarra, F. Piselli, Mutual visibility in hypercube-like graphs, Structural Information and Communication Complexity. SIROCCO 2024

    work page 2024

  19. [19]

    Cicerone, G

    S. Cicerone, G. Di Stefano, S. Klavˇ zar, I.G. Yero, Mutual-visibility problems on graphs of diameter two, Eur. J. Comb. 120 (2024) 103995

    work page 2024

  20. [20]

    Breˇ sar, I.G

    B. Breˇ sar, I.G. Yero, Lower (total) mutual-visibility number in graphs, Appl. Math. Comput. 456 (2024) 128411.doi: 10.1016/j.amc.2023.128411

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

  21. [21]

    Boruzanlı Ekinci, Cs

    G. Boruzanlı Ekinci, Cs. Bujt´ as, Mutual-visibility problems in Kneser and Johnson graphs, Ars. Math. Contemp. (2024) doi.org/10.26493/1855-3974.3344.4c8

    work page doi:10.26493/1855-3974.3344.4c8 2024

  22. [22]

    Cicerone, G

    S. Cicerone, G. Di Stefano, S. Klavˇ zar, On the mutual-visibility in Cartesian products and in triangle-free graphs, Appl. Math. Comput. 438 (2023) Paper 127619. doi: 10.1016/j.amc.2022.127619

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

  23. [23]

    Kuziak, D., Rodr´ ıguez-Vel´ azquez, J.A.: Total mutual-visibility in graphs with emphasis on lexicographic and Carte- sian products. Bull. Malays. Math. Sci. Soc. 46, 197 (2023). doi: 10.1007/s40840-023-01590-3

    work page doi:10.1007/s40840-023-01590-3 2023

  24. [24]

    Opuscula Math 45, 63–78 (2025)

    Bujt´ as, Cs., Klavˇ zar, S., Tian, J.: Total mutual-visibility in Hamming graphs. Opuscula Math 45, 63–78 (2025)

    work page 2025

  25. [25]

    Csilla Bujt´ asa, Sandi Klavˇ zara, Jing Tiand,Visibility polynomials, dual visibility spectrum, and characterization of total mutual-visibility sets ,arXiv:2412.03066v1 [math.CO], Dec 2024

    work page arXiv 2024

  26. [26]

    Harary , Graph Theory, Addison-Wesley, 1969

    F. Harary , Graph Theory, Addison-Wesley, 1969 . Tonny K B, Department of Mathematics, College of Engineering Trivandrum, Thiruvananthapuram, Kerala, India, 695016. Email address: tonnykbd@cet.ac.in Shikhi M, Department of Mathematics, College of Engineering Trivandrum, Thiruvananthapuram, Kerala, India, 695016. Email address: shikhim@cet.ac.in

    work page 1969