Geodesic
On the vertex position number of graphs
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 1169-1188 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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 ⊆ V(G) is an x-position set if for any y ∈ S the shortest x,y-paths in G contain no point of S∖{ 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 
@article{DMGT_2024_44_3_a17,
     author = {Thankachy, Maya G. S. and Chandran S.V., Ullas and Tuite, James and Thomas, Elias and Di Stefano, Gabriele and Erskine, Grahame},
     title = {On the vertex position number of graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1169--1188},
     year = {2024},
     volume = {44},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a17/}
}
TY  - JOUR
AU  - Thankachy, Maya G. S.
AU  - Chandran S.V., Ullas
AU  - Tuite, James
AU  - Thomas, Elias
AU  - Di Stefano, Gabriele
AU  - Erskine, Grahame
TI  - On the vertex position number of graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 1169
EP  - 1188
VL  - 44
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a17/
LA  - en
ID  - DMGT_2024_44_3_a17
ER  - 
%0 Journal Article
%A Thankachy, Maya G. S.
%A Chandran S.V., Ullas
%A Tuite, James
%A Thomas, Elias
%A Di Stefano, Gabriele
%A Erskine, Grahame
%T On the vertex position number of graphs
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 1169-1188
%V 44
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a17/
%G en
%F DMGT_2024_44_3_a17
Thankachy, Maya G. S.; Chandran S.V., Ullas; Tuite, James; Thomas, Elias; Di Stefano, Gabriele; Erskine, Grahame. On the vertex position number of graphs. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 1169-1188. http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a17/

[1] 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

[2] T.M. Apostol, Introduction to Analytic Number Theory (Springer-Verlag, New York, 1976). https://doi.org/10.1007/978-1-4757-5579-4

[3] V.G. Boltjansky and I. Gohberg, Results and Problems in Combinatorial Geometry (Cambridge University Press, Cambridge, 1985). https://doi.org/10.1017/CBO9780511569258

[4] F. Buckley and F. Harary, Distance in Graphs (Addison-Wesley, Redwood City, CA, 1990).

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

[6] G. Chartrand and P. Zhang, Introduction to Graph Theory (Tata McGraw-Hill Pub. Co., New Delhi, 2006).

[7] G. Di Stefano, Mutual visibility in graphs, Appl. Math. Comput. 419 (2022) 126850. https://doi.org/10.1016/j.amc.2021.126850

[8] H.E. Dudeney, Amusements in Mathematics (T. Nelson and Sons, Ltd., London, 1917).

[9] P. Erdős, P.M. Gruber and J. Hammer, Lattice Points (Longman Scientific & Technical, Harlow, 1989).

[10] 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

[11] 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

[12] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Academic Press, New York, 1980). https://doi.org/10.1016/C2013-0-10739-8

[13] J. Hammer, Unsolved Problems Concerning Lattice Points, in: Res. Notes Math. 15 (Publishing Ltd., London, 1977).

[14] G.H. Hardy, E.M. Wright, J. Silverman and A. Wiles, An Introduction to the Theory of Numbers (Oxford University Press, Oxford, 2008).

[15] 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

[16] 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

[17] 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

[18] 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

[19] J. O'Rourke, Art Gallery Theorems and Algorithms (Oxford University Press, New York, Oxford, 1987).

[20] 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.

[21] 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

[22] 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

[23] 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