A GENERAL POSITION PROBLEM IN GRAPH THEORY
By P. Manuel, S. Klavžar. Bulletin of the Australian Mathematical Society, 2018
93 citations recorded by the source corpus.
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.
Subfields: Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design
View Paper: https://www.semanticscholar.org/paper/aec03b62900277709b10793a168058c5d05fd34f
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
Citations in the corpus
- On General Position Sets in Cartesian Products (2019, background): “The problem was independently introduced in [13,25], the present terminology and formalism are from [13].”