DMGT

In this paper we generalise the notion of visibility from a point in an integer lattice to the setting of graph theory. For a vertex $x$ of a graph $G$, we say that a set $S \subseteq V(G)$ is an $x$-position set if for any $y \in S$ the shortest $x,y$-paths in $G$ contain no point of $S\setminus \{ y\}$. We investigate the largest and smallest orders of maximum $x$-position sets in graphs, determining these numbers for common classes of graphs and giving bounds in terms of the girth, vertex degrees, diameter and radius. Finally we discuss the complexity of finding maximum vertex position sets in graphs.

Keywords:

geodesic, vertex position set, vertex position number, general position number

References:

B.S. Anand, U. Chandran S.V., M. Changat, S. Klavžar and E.J. Thomas, Characterization of general position sets and its applications to cographs and bipartite graphs., Appl. Math. Comput. 359 (2019) 84–89.
https://doi.org/10.1016/j.amc.2019.04.064
T.M. Apostol, Introduction to Analytic Number Theory (Springer-Verlag, New York, 1976).
https://doi.org/10.1007/978-1-4757-5579-4
V.G. Boltjansky and I. Gohberg, Results and Problems in Combinatorial Geometry (Cambridge University Press, Cambridge, 1985).
https://doi.org/10.1017/CBO9780511569258
F. Buckley and F. Harary, Distance in Graphs (Addison-Wesley, Redwood City, CA, 1990).
U. Chandran S.V. and G.J. Parthasarathy, The geodesic irredundant sets in graphs, Int. J. Math. Combin. 4 (2016) 135–143.
G. Chartrand and P. Zhang, Introduction to Graph Theory (Tata McGraw-Hill Pub. Co., New Delhi, 2006).
G. Di Stefano, Mutual visibility in graphs, Appl. Math. Comput. 419 (2022) 126850.
https://doi.org/10.1016/j.amc.2021.126850
H.E. Dudeney, Amusements in Mathematics (T. Nelson and Sons, Ltd., London, 1917).
P. Erdős, P.M. Gruber and J. Hammer, Lattice Points (Longman Scientific $\&$ Technical, Harlow, 1989).
V. Froese, I. Kanj, A. Nichterlein and R. Niedermeier, Finding points in general position, Internat. J. Comput. Geom. Appl. 27 (2017) 277–296.
https://doi.org/10.1142/S021819591750008X
M. Ghorbani, H.R. Maimani, M. Momeni, F.R. Mahid, S. Klavžar and G. Rus, The general position problem on Kneser graphs and on some graph operations, Discuss. Math. Graph Theory 41 (2021) 1199–1213.
https://doi.org/10.7151/dmgt.2269
M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Academic Press, New York, 1980).
https://doi.org/10.1016/C2013-0-10739-8
J. Hammer, Unsolved Problems Concerning Lattice Points, in: Res. Notes Math. 15 (Publishing Ltd., London, 1977).
G.H. Hardy, E.M. Wright, J. Silverman and A. Wiles, An Introduction to the Theory of Numbers (Oxford University Press, Oxford, 2008).
P. Manuel and S. Klavžar, A general position problem in graph theory, Bull. Aust. Math. Soc. 98 (2018) 177–187.
https://doi.org/10.1017/S0004972718000473
P. Manuel and S. Klavžar, The graph theory general position problem on some interconnection networks, Fund. Inform. 163 (2018) 339–350.
https://doi.org/10.3233/FI-2018-1748
B. Patkós, On the general position problem on Kneser graphs, Ars Math. Contemp. 18 (2020) 273–280.
https://doi.org/10.26493/1855-3974.1957.a0f
M.S. Payne and D.R. Wood, On the general position subset selection problem, SIAM J. Discrete Math. 27 (2013) 1727–1733.
https://doi.org/10.1137/120897493
J. O'Rourke, Art Gallery Theorems and Algorithms (Oxford University Press, New York, Oxford, 1987).
J.J. Sylvester, Sur le nombre de fractions ordinaires inégales qu'on peut exprimer en se servant de chiffres qui n’excèdent pas un nombre donné, C.R. Acad. Sci. Paris 96 (1883) 409–413.
E.J. Thomas and U. Chandran S.V., Characterization of classes of graphs with large general position number, AKCE Int. J. Graphs Comb. 17 (2020) 935–939.
https://doi.org/10.1016/j.akcej.2019.08.008
J. Tian and K. Xu, The general position number of Cartesian products involving a factor with small diameter, Appl. Math. Comput. 403 (2021) 126206.
https://doi.org/10.1016/j.amc.2021.126206
J. Tian, K. Xu and S. Klavžar, The general position number of the Cartesian product of two trees, Bull. Aust. Math. Soc. 104 (2021) 1–10.
https://doi.org/10.1017/S0004972720001276