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.

DOI: https://doi.org/10.1007/978-3-030-95018-7_4

Abstract

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

Metrics

Item Actions

Export

You can export this page using these formats Digital Object Identifier - DOI

About

• Item ORO ID
• 82211
• Item Type
• Conference or Workshop Item
• ISSN
• 0302-9743
• Keywords
• General position; Monophonic position; Turán problems; Size Diameter; Induced path
• Academic Unit or School
• Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
  Faculty of Science, Technology, Engineering and Mathematics (STEM)
• Copyright Holders
• © Springer Nature Switzerland AG 2022
• Depositing User
• ORO Import