Some Position Problems for Graphs

Tuite, James; Thomas, Elias John and Chandran S. V., Ullas (2022). Some Position Problems for Graphs. In: Algorithms and Discrete Applied Mathematics: 8th International Conference, CALDAM 2022, 10-12 Feb 2022, Puducherry, India, pp. 36–47.



The general position problem for graphs stems from a puzzle of Dudeney and the general position problem from discrete geometry. The general position number of a graph G is the size of the largest set of vertices S such that no geodesic of G contains more than two elements of S. The monophonic position number of a graph is defined similarly, but with ‘induced path’ in place of ‘geodesic’. In this abstract we discuss the smallest possible order of a graph with given general and monophonic position numbers, determine the asymptotic order of the largest size of a graph with given order and position numbers and finally determine the possible diameters of a graph with given order and monophonic position number.

Viewing alternatives


Public Attention

Altmetrics from Altmetric

Number of Citations

Citations from Dimensions
No digital document available to download for this item

Item Actions