1 results
A GENERAL POSITION PROBLEM IN GRAPH THEORY
- Part of
-
- Journal:
- Bulletin of the Australian Mathematical Society / Volume 98 / Issue 2 / October 2018
- Published online by Cambridge University Press:
- 18 July 2018, pp. 177-187
- Print publication:
- October 2018
-
- Article
-
- You have access
- Export citation
-
The paper introduces a graph theory variation of the general position problem: given a graph
$G$, determine a largest set 
$S$ of vertices of 
$G$ such that no three vertices of 
$S$ lie on a common geodesic. Such a set is a max-gp-set of 
$G$ and its size is the gp-number 
$\text{gp}(G)$ of 
$G$. Upper bounds on 
$\text{gp}(G)$ in terms of different isometric covers are given and used to determine the gp-number of several classes of graphs. Connections between general position sets and packings are investigated and used to give lower bounds on the gp-number. It is also proved that the general position problem is NP-complete.
