ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 21 (2021) #P1.03 / 33–44
https://doi.org/10.26493/1855-3974.2384.77d
(Also available at http://amc-journal.eu)
General d-position sets*
Sandi Klavžar
Faculty of Mathematics and Physics, University of Ljubljana, Slovenia, and
Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia, and
Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia
Douglas F. Rall
Department of Mathematics, Furman University, Greenville, SC, USA
Ismael G. Yero †
Departamento de Matemáticas, Universidad de Cádiz, Algeciras, Spain
Received 17 July 2020, accepted 14 February 2021, published online 10 August 2021
Abstract
The general d-position number gpd(G) of a graph G is the cardinality of a largest set
S for which no three distinct vertices from S lie on a common geodesic of length at most
d. This new graph parameter generalizes the well studied general position number. We first
give some results concerning the monotonic behavior of gpd(G)with respect to the suitable
values of d. We show that the decision problem concerning finding gpd(G) is NP-complete
for any value of d. The value of gpd(G) when G is a path or a cycle is computed and a
structural characterization of general d-position sets is shown. Moreover, we present some
relationships with other topics including strong resolving graphs and dissociation sets. We
finish our exposition by proving that gpd(G) is infinite wheneverG is an infinite graph and
d is a finite integer.
Keywords: General d-position sets, dissociation sets, strong resolving graphs, computational com-
plexity, infinite graphs.
Math. Subj. Class. (2020): 05C12, 05C63, 05C69
*We acknowledge the financial support from the Slovenian Research Agency (research core funding No. P1-
0297 and projects J1-9109, J1-1693, N1-0095, N1-0108). This research was initiated while the third author was
visiting the University of Ljubljana, Slovenia, supported by “Ministerio de Educación, Cultura y Deporte”, Spain,
under the “José Castillejo” program for young researchers (reference number: CAS18/00030).
†Corresponding author.
E-mail addresses: sandi.klavzar@fmf.uni-lj.si (Sandi Klavžar), doug.rall@furman.edu (Douglas F. Rall),
ismael.gonzalez@uca.es (Ismael G. Yero)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
34 Ars Math. Contemp. 21 (2021) #P1.03 / 33–44
1 Introduction
A general position set of a graph G is a set of vertices S ⊆ V (G) such that no three
vertices from S lie on a common shortest path of G. The order of a largest general po-
sition set, shortly called a gp-set, is the general position number gp(G) of G (also writ-
ten gp-number). This concept was recently and independently introduced in [6, 16]. We
should mention though that the same concept was studied on hypercubes already in 1995
by Körner [14]. Following [16] and its notation and terminology, the concept received a lot
of attention, see the series of papers [8, 13, 11, 12, 17, 18, 21, 22]. In particular, in [18] the
general position problem was studied on complementary prisms. In order to characterize
an extremal case for the general position number of these graphs, the concept of general
3-position was introduced as an essential ingredient of the characterization. In this paper
we extend this idea as follows.
Let d ∈ N and let G be a (connected) graph. Then S ⊆ V (G) is a general d-position set
if the following holds:
{u, v,w} ∈ (S
3
), v ∈ IG(u,w)⇒ dG(u,w) > d , (1.1)
where dG(u,w) denotes the shortest-path distance in G between u and w, and IG(u,w) =
{x ∈ V (G) ∶ dG(u,w) = dG(u,x)+dG(x,w)} is the interval between u and w. In words,
S is a general d-position set if no three different vertices from S lie on a common geodesic
of length at most d. We will say that vertices u, v,w that fulfill condition (1.1) lie in general
d-position. The cardinality of a largest general d-position set in a graph G is the general
d-position number of G and is denoted by gpd(G).
We proceed as follows. In the rest of this section we recall needed definitions and state
some basic facts and results on the general d-position number. Then, in Section 2, we
demonstrate that in the inequality chain gpdiam(G)(G) ≤ gpdiam(G)−1(G) ≤ ⋯ ≤ gp2(G)
all kinds of equality and strict inequality cases are possible. Using one of the correspond-
ing constructions we also prove that the problem of determining the gpd number is NP-
complete. In Section 3 we determine the gpd number of paths and cycles and give a general
upper bound on the gpd number in term of the diameter of a given graph. In the subsequent
section we prove a structural characterization of general d-position sets. In Section 5 we
report on the connections between general d-position sets and two well-established con-
cepts, the dissociation number and strong resolving graphs. In the concluding section we
consider the gpd number of infinite graphs and pose several open questions.
1.1 Preliminaries
For a positive integer k we will use the notation [k] = {1, . . . , k}. The clique number and
the independence number ofG are denoted by ω(G) and α(G). If S ⊆ V (G), then the sub-
graph ofG induced by S is denoted by ⟨S⟩ and (S
k
) denotes the set of all subsets of S having
cardinality k. A subgraph H of a graph G is isometric if dH(u, v) = dG(u, v) holds for all
u, v ∈ V (H). If H1 and H2 are subgraphs of G, then the distance dG(H1,H2) between
H1 and H2 is defined as min{dG(h1, h2) ∶ h1 ∈ V (H1), h2 ∈ V (H2)}. In particular, if
H1 is the one vertex graph with u being its unique vertex, then we will write dG(u,H2) for
dG(H1,H2). We say that the subgraphs H1 and H2 are parallel, denoted by H1 ∥ H2, if
for every pair of vertices h1 ∈ V (H1) and h2 ∈ V (H2)we have dG(h1, h2) = dG(H1,H2).
If H1 and H2 are not parallel, we will write H1 ∦ H2. The open neighborhood and the
S. Klavžar et al.: General d-position sets 35
closed neighborhood of a vertex v of G will be denoted by NG(x) and NG[x], respec-
tively. Vertices x and y of G are true twins if NG[u] = NG[v]. We may omit the subscript
G in the above definitions if the graph G is clear from the context.
Clearly, if d = 1, then every subset of vertices of G is a general 1-position set, and if
d ≥ diam(G), then S is a general d-position set if and only if S is a general position set.
Moreover, note that
gpdiam(G)(G) ≤ gpdiam(G)−1(G) ≤ ⋯ ≤ gp2(G) . (1.2)
We conclude the preliminaries with the following useful property.
Proposition 1.1. Let G be a graph and let 2 ≤ d ≤ diam(G) − 1 be a positive integer.
If H1, . . . ,Hr are isometric subgraphs of G such that dG(Hi,Hj) ≥ d for i ≠ j, then
gpd(G) ≥ ∑ri=1 gpd(Hi).
Proof. For each i ∈ [r], let Si be a general d-position set of Hi such that ∣Si∣ = gpd(Hi).
We claim that S = ⋃ri=1 Si is a general d-position set of G. Suppose {x, y, z} ∈ (S3) such
that y ∈ IG(x, z) and dG(x, z) ≤ d. That is, there exists a shortest x, z-path of length
at most d in G that contains y. Since dG(u, v) ≥ d for any two vertices u ∈ V (Hi) and
v ∈ V (Hj) with i ≠ j, there exists k ∈ [r] such that {x, y, z} ⊆ V (Hk). Now, since Hk
is an isometric subgraph of G, it follows that dHk(x, y) = dG(x, y), dHk(y, z) = dG(y, z)
and dHk(x, z) = dG(x, z). This implies that there is a x, z-geodesic in Hk that contains
y. Hence, y ∈ IHk(x, z), and since Sk is a general d-position set of Hk, we infer that
dG(x, z) = dHk(x, z) > d, which is a contradiction. Therefore, S is a general d-position
set of G, and it follows that gpd(G) ≥ ∑ri=1 gpd(Hi).
2 On the inequality chain (1.2) and computational complexity
In this section we investigate the inequality chain (1.2) by constructing different classes of
graphs which demonstrate that all kinds of equality and strict inequality cases can happen.
We conclude the section by applying one of these constructions to prove that the GENERAL
d-POSITION PROBLEM is NP-complete.
Equality in (1.2) simultaneously.
For n ≥ 2, let S be a star with center x and leaves u1, . . . , un, v1, . . . , vn. Construct a graph
Gn of order 2n + 3 by taking the disjoint union of S and an independent set of vertices
{u, v} together with the set of edges {uui, vvi ∶ i ∈ [n]}. The diameter of Gn is 4, and we
have gp4(Gn) = gp3(Gn) = gp2(Gn) = 2n.
Equality in (1.2) simultaneously again.
Let Tr, r ≥ 2, be the tree obtained from the path Pr+1 on r + 1 vertices, by attaching two
leaves to each of its internal vertices. Then we claim that
gpr(Tr) = gpr−1(Tr) = ⋯ = gp2(Tr) .
Indeed, first note that diam(Tr) = r. Since the gp-number of a tree is the number of its
leaves (cf. [16, Corollary 3.7]), we have gpr(Tr) = 2r. Let next S be a general 2-position
set. If u is a vertex of Tr adjacent to exactly two leaves, say v andw, then ∣S∩{u, v,w}∣ ≤ 2.
Moreover, if u is a vertex of Tr adjacent to exactly three leaves, say v, w, and z, then
∣S ∩ {u, v,w, z}∣ ≤ 3. It follows that gp2(Tr) ≤ 2(r − 3) + 2 ⋅ 3 = 2r. In conclusion,
2r = gpr(Tr) ≤ gpr−1(Tr) ≤ ⋯ ≤ gp2(Tr) ≤ 2r, hence equality holds throughout.
36 Ars Math. Contemp. 21 (2021) #P1.03 / 33–44
Strict inequality in (1.2) in exactly one case.
Let k, ℓ ≥ 4 and let Gk,ℓ be a graph defined as follows. Its vertex set is
V (Gk,ℓ) =
k
⋃
j=1
{uj ,wj , xj,1, . . . , xj,ℓ} ∪ {xk+1,1} .
For j ∈ [k], each of the vertices uj and wj is adjacent to xj,1, . . . , xj,ℓ and to xj+1,1. There
are no other edges in Gk,ℓ. Note that ∣V (Gk,ℓ)∣ = k(ℓ + 2) + 1 and that diam(Gk,ℓ) = 2k.
It is straightforward to see that the set X = ⋃kj=1{xj,1, . . . , xj,ℓ} ∪ {xk+1,1} is a largest
independent set of Gk,ℓ. Moreover, X is also a largest general 2-position set and a largest
general 3-position set. Furthermore, it is not difficult to infer that the setX∖{x2,1, . . . , xk,1}
is a largest general d-position set for each d ∈ {4, . . . ,2k}. In conclusion,
gp2k(Gk,ℓ) = gp2k−1(Gk,ℓ) = ⋯ = gp4(Gk,ℓ) < gp3(Gk,ℓ) = gp2(Gk,ℓ) = α(G) .
Strict inequality in (1.2) in every case.
Given a positive integer t, construct the graph Ht as follows. Begin with a complete graph
K4t with vertex set V (K4t) = A ∪ B where ∣A∣ = ∣B∣ = 2t. Next, add a path Pt−1 =
v1 . . . vt−1, and join with an edge every vertex of B with the leaf v1 of Pt−1. Then, add a
pendant vertex ui to every vertex vi ∈ {v2, . . . , vt−1}, and finally, for every i ∈ {2, . . . , t−1},
add the edge uivi−1. As an example, the graph H8 is represented in Figure 1.
A B
v7v6v5v4v3v2v1
u7u6u5u4u3u2
Figure 1: The graph H8. Edges joining the sets A and B, as well as joining B with the
vertex v1 are indicated with dotted lines.
Notice that the graph Ht has diameter t. The general d-position number of Ht for all
possible d is given in the following result.
Proposition 2.1. If 2 ≤ d ≤ t, then
gpd(Ht) =
⎧⎪⎪⎪⎨⎪⎪⎪⎩
4t; d = t,
4t + 2; d = t − 1,
5t − d + 1; otherwise.
Proof. We first note that the set A ∪ B is a general position set of Ht, or equivalently a
general t-position set. Thus, gp(Ht) = gpt(Ht) ≥ 4t. Suppose gp(Ht) = gpt(Ht) > 4t
and let S be a general t-position set. Hence, there exists at least one vertex not in A ∪ B
which is in S. Since every shortest path joining a vertex of A with a vertex not in A ∪B
passes through a vertex in B, it follows that S ∩ A = ∅ or S ∩ B = ∅. This implies that
∣S∣ ≤ 2t+2t−3 = 4t−3, and this is not possible. Therefore gp(Ht) = gpt(Ht) = 4t = 5t−d,
when d = t.
S. Klavžar et al.: General d-position sets 37
We next consider the case d = t − 1. The set A ∪B ∪ {vt−1, ut−1} is a general (t − 1)-
position set of Ht, and so, gpt−1(Ht) ≥ 4t+2. If we suppose that gpt−1(Ht) > 4t+2, then
a similar argument to that above for d = t leads to a contradiction. Therefore, gpt−1(Ht) =
4t + 2.
We finally consider d = t − k with 2 ≤ k ≤ t − 2. Notice that the set A ∪ B ∪
{vt−1, ut−1, ut−2, . . . , ut−k} is a general d-position set of Ht of cardinality 4t + k + 1 =
4t + (t − d + 1) = 5t − d + 1, and so, gpd(Ht) ≥ 5t − d + 1. Again, an argument similar to
the two cases above leads to gpd(Ht) = 5t − d + 1.
Proposition 2.1 yields strict inequalities in the chain (1.2), that is, for any graphHt with
t ≥ 3, we have
gpt(Ht) < gpt−1(Ht) < ⋯ < gp2(Ht) . (2.1)
We shall finish this section by considering the computational complexity of the decision
problem related to finding the general d-position number of graphs, in which we also show
the usefulness of the above graphs Ht.
GENERAL d-POSITION PROBLEM
Input: A graph G, an integer d ≥ 2, and a positive integer r.
Question: Is gpd(G) larger than r?
We first remark that the GENERAL d-POSITION PROBLEM is known to be NP-complete
for every d ≥ diam(G) (see [16]). Hence, we may center our attention on the cases d ∈
{2, . . . ,diam(G) − 1}, although our reduction also works for the case d = diam(G).
Theorem 2.2. If d ≥ 2, then the GENERAL d-POSITION PROBLEM is NP-complete.
Proof. First, we can readily observe that the problem belongs to the class NP, since check-
ing that a given set is indeed a general d-position set can be done in polynomial time. From
now on, we make a reduction from the MAXIMUM CLIQUE PROBLEM to the GENERAL
d-POSITION PROBLEM.
In order to present the reduction, for a given graph G of order t ≥ 3, we shall construct
a graph G′ by using the above graphs Ht. We construct G′ from the disjoint union of G
and Ht, by adding all possible edges between A ∪ B ∪ {v1} and V (G). It is then easily
observed that ω(G′) = ∣A∣+ ∣B∣+ω(G). Moreover, using similar arguments as in the proof
of Proposition 2.1, we deduce that gpd(G′) = gpd(Ht) + ω(G). From this fact, since the
value gpd(Ht) is known from Proposition 2.1, the reduction is completed, and the theorem
is proved.
3 Paths and cycles
In this section we determine the general d-position number of paths and cycles. The first
result in turn implies a general upper bound on the general d-position number in term of
the diameter of a given graph.
Proposition 3.1. If n ≥ 3 and 2 ≤ d ≤ n − 1, then
gpd(Pn) =
⎧⎪⎪⎨⎪⎪⎩
2 ⌈ n
d+1⌉ − 1; n ≡ 1 (mod d + 1),
2 ⌈ n
d+1⌉ ; otherwise.
38 Ars Math. Contemp. 21 (2021) #P1.03 / 33–44
Proof. Let d ∈ {2, . . . , n − 1} and Pn = v1v2 . . . vn. If n ≡ 1 (mod d + 1), then let
S = {v(d+1)i+1, v(d+1)i+2 ∶ 0 ≤ i ≤ ⌊n/(d + 1)⌋ − 1} ∪ {vn} ,
and if n /≡ 1 (mod d + 1), then let
S = {v(d+1)i+1, v(d+1)i+2 ∶ 0 ≤ i ≤ ⌈n/(d + 1)⌉ − 1} .
It can be readily seen that S is a general d-position set of Pn, which gives the lower bound
gpd(Pn) ≥
⎧⎪⎪⎨⎪⎪⎩
2 ⌈ n
d+1⌉ − 1; n ≡ 1 (mod d + 1),
2 ⌈ n
d+1⌉ ; otherwise.
On the other hand, suppose
gpd(Pn) >
⎧⎪⎪⎨⎪⎪⎩
2 ⌈ n
d+1⌉ − 1; n ≡ 1 (mod d + 1),
2 ⌈ n
d+1⌉ ; otherwise,
and let S′ be a general d-position set of cardinality gpd(Pn). By the pigeonhole principle,
we deduce that there exists a subpath in Pn of length d that contains at least three elements
of S′, but this is not possible. Therefore, the desired equality follows.
Specializing to n = 14 in Proposition 3.1, we next show a table with the values of
gpd(Pn) for every possible value of d. Notice that, equalities and inequalities occur in
distinct positions with respect to the chain (1.2).
d 2 3 4 5 6 7 8 9 10 11 12 13
gpd(P14) 10 8 6 6 4 4 4 4 4 4 3 2
Table 1: The values of gpd(P14) for every 2 ≤ d ≤ 13.
The result for paths gives the following general lower bound.
Corollary 3.2. Let G be a connected graph of diameter d. If 2 ≤ k ≤ d, then
gpk(G) ≥
⎧⎪⎪⎨⎪⎪⎩
2 ⌈ d+1
k+1⌉ − 1; d ≡ 0 (mod k + 1),
2 ⌈ d+1
k+1⌉ ; otherwise.
Proof. Shortest paths are isometric subgraphs; in particular, this holds for diametrical
paths. Hence G contains an isometric Pd+1, and therefore gpk(G) ≥ gpk(Pd+1) by Propo-
sition 1.1 with r = 1. Applying Proposition 3.1 yields the result.
In a similar manner as done for paths, we can compute the general d-position number
for cycles. It is easy to show that gpd(C3) = 3 for any d, gp1(C4) = 4, and gpd(C4) = 2
for d ≥ 2.
Proposition 3.3. If n ≥ 5 and 2 ≤ d < ⌊n
2
⌋, then
gpd(Cn) =
⎧⎪⎪⎨⎪⎪⎩
2 ⌊ n
d+1⌋ + 1; n ≡ d (mod d + 1),
2 ⌊ n
d+1⌋ ; otherwise.
If d ≥ ⌊n
2
⌋, then gpd(Cn) = 3.
S. Klavžar et al.: General d-position sets 39
Proof. Let Cn = v1v2 . . . vnv1. Note that diam(Cn) = ⌊n2 ⌋, and the argument naturally
splits into two cases.
First assume that 2 ≤ d < ⌊n
2
⌋. Let m = ⌊ n
d+1⌋ and for each k ∈ [m] we define Xk
by Xk = {vi ∶ (k − 1)(d + 1) + 1 ≤ i ≤ k(d + 1)}. Let X = V (Cn) ∖ ⋃mk=1Xk. Note
that ∣X ∣ = x where n ≡ x (mod d + 1) and x is the unique integer such that 0 ≤ x ≤ d.
If x ≠ d, then let S = {v(k−1)(d+1)+1, v(k−1)(d+1)+2 ∶ 1 ≤ k ≤ m}. If x = d, then let
S = {v(k−1)(d+1)+1, v(k−1)(d+1)+2 ∶ 1 ≤ k ≤ m} ∪ {vm(d+1)+1}. It is straightforward to
check that in both cases S is a general d-position set, which shows that the claimed value
is a lower bound for gpd(Cn). As in the proof of Proposition 3.1, an application of the
pigeonhole principle establishes the upper bound.
Since diam(Cn) = ⌊n2 ⌋, to prove the second statement it is sufficient to show that
gpd(Cn) = 3 for d = ⌊n2 ⌋. For this purpose, let S = {v1, v3, v⌈n2 ⌉+2}. For n = 2r, we see that
S = {v1, v3, vr+2} and d = r. On the other hand, for n = 2r + 1, we have S = {v1, v3, vr+3}
and d = r. In both cases an easy computation shows that none of the three vertices lies on a
shortest path in Cn between the other two vertices. Therefore, S is a general d-position set,
and it follows that gpd(Cn) ≥ 3. Suppose T is an arbitrary general d-position set ofCn. We
may assume without loss of generality that v1 ∈ T . It follows that ∣T ∩ {v2, . . . , vr+1}∣ ≤ 1
and ∣T ∩ {vr+2, . . . vn}∣ ≤ 1, for otherwise T contains three vertices that lie on a path of
length at most d. Therefore, gpd(Cn) ≤ ∣T ∣ ≤ 3.
4 A characterization of general d-position sets
In [1, Theorem 3.1] a structural characterization of general position sets of a given graph
was proved. In this section we give such a characterization for general d-position sets and
as a consequence deduce the characterization from [1].
Theorem 4.1. Let G be a connected graph and let d ≥ 2 be an integer. Then S ⊆ V (G) is
a general d-position set if and only if the following conditions hold:
(i) ⟨S⟩ is a disjoint union of complete graphs Q1, . . . ,Qℓ.
(ii) If Qi ∦ Qj , i ≠ j, then dG(Qi,Qj) ≥ d.
(iii) If dG(Qi,Qj) + dG(Qj ,Qk) = dG(Qi,Qk) for {i, j, k} ∈ ([ℓ]3 ), then dG(Qi,Qk) >
d.
Proof. Let S be a general d-position set of G and let H be a connected component of ⟨S⟩.
If H is not complete, then it contains an induced P3. The vertices of this P3 are on a
geodesic of length 2 which is not possible since they belong to S and d ≥ 2. Hence H must
be complete.
Consider next two cliques Qi and Qj that are not parallel. Let dG(Qi,Qj) = p and let
u ∈ Qi and v ∈ Qj be vertices with dG(u, v) = p. Since Qi ∦ Qj , we may assume without
loss of generality that there is a vertex w ∈ Qi such that dG(w,Qj) = p + 1. Then u lies on
a w, v-geodesic of length p+1 which implies that p+1 ≥ d+1 and so, dG(Qi,Qj) = p ≥ d.
Assume next that dG(Qi,Qj)+dG(Qj ,Qk) = dG(Qi,Qk) for some {i, j, k} ∈ ([ℓ]3 ). If
Qi ∦ Qj , then by the already proved condition (ii) we immediately get that dG(Qi,Qj) ≥ d
and thus dG(Qi,Qk) > d. The same holds if Qj ∦ Qk. Hence assume next that Qi ∥
Qj and Qj ∥ Qk. Let u ∈ Qi and w ∈ Qk be vertices with dG(u,w) = dG(Qi,Qk).
Since dG(Qi,Qj) + dG(Qj ,Qk) = dG(Qi,Qk), Qi ∥ Qj , and Qj ∥ Qk, it follows that
40 Ars Math. Contemp. 21 (2021) #P1.03 / 33–44
dG(u,w) = dG(u, v)+dG(v,w) for every vertex v ofQj . We conclude that dG(Qi,Qk) >
d.
To prove the converse, assume that conditions (i), (ii), and (iii) are fulfilled for a given
set S and let {u, v,w} ∈ (S
3
). We need to show that u, v,w lie in general d-position.
If u, v,w lie in the same connected component of ⟨S⟩, then by (i), this component is
complete and the assertion is clear. Suppose next that u, v,w lie in the union of cliques Qi
and Qj . If Qi ∥ Qj , then u, v,w are clearly in general d-position. And if Qi ∦ Qj , then
u, v,w lie in general d-position by (ii).
In the last case to consider the three vertices lie in different cliques, say u ∈ Qi, v ∈ Qj ,
andw ∈ Qk. If the assertion does not hold, then the three vertices lie on a common geodesic
and we may assume without loss of generality that dG(u,w) = dG(u, v) + dG(v,w). If
Qi ∦ Qj , then by (ii), we get dG(Qi,Qj) ≥ d and hence dG(u,w) = dG(u, v)+dG(v,w) ≥
dG(Qi,Qj)+dG(Qj ,Qk) ≥ d+1 > d. Analogously, ifQj ∦ Qk, we also get dG(u,w) > d.
Suppose then that Qi ∥ Qj and Qj ∥ Qk. If also Qi ∥ Qk, then dG(u,w) = dG(u, v) +
dG(v,w) implies that dG(Qi,Qj) + dG(Qj ,Qk) = dG(Qi,Qk) and so dG(Qi,Qk) > d
by (iii). Again using the fact that Qi ∥ Qk, it follows that dG(u,w) > d. We are left with
the case that Qi ∥ Qj , Qj ∥ Qk, and Qi ∦ Qk. If dG(u,w) = dG(Qi,Qk), then by (iii),
we get that dG(u,w) > d. Otherwise we may assume without loss of generality that there
exists a vertex u′ ∈ Qi, u′ ≠ u, such that dG(Qi,Qk) = dG(u′,Qk) < dG(u,w). Since
Qi ∦ Qk, (ii) implies that dG(u′,Qk) ≥ d. But then dG(u,w) > dG(Qi,Qk) ≥ d.
Corollary 4.2 ([1, Theorem 3.1]). Let G be a connected graph. Then S ⊆ V (G) is a
general position set if and only if the following conditions hold:
(i) ⟨S⟩ is a disjoint union of complete graphs Q1, . . . ,Qℓ.
(ii) Qi ∥ Qj for every i ≠ j.
(iii) dG(Qi,Qj) + dG(Qj ,Qk) ≠ dG(Qi,Qk) for every {i, j, k} ∈ ([ℓ]3 ).
Proof. Set d = diam(G), so that general d-position sets are precisely general position sets.
Condition (ii) of Theorem 4.1 implies that in cliques Qi and Qj , which are not parallel,
we can find a pair of vertices at distance larger than diam(G). Since this is not possible,
every two cliques must be parallel. Similarly, if the assumption of condition (iii) would be
fulfilled for some cliques Qi, Qj , and Qk, then we would again have vertices at distance
larger than diam(G). Therefore, dG(Qi,Qj) + dG(Qj ,Qk) ≠ dG(Qi,Qk) must hold for
every {i, j, k} ∈ ([ℓ]
3
).
5 Connections with other topics
In this section we connect general d-position sets with the dissociation number and with
strong resolving graphs.
Strong resolving graphs
A vertex u of a connected graph G is maximally distant from a vertex v if every w ∈ N(u)
satisfies dG(v,w) ≤ dG(u, v). If u is maximally distant from v, and v is maximally distant
from u, then u and v are mutually maximally distant (MMD for short). Given an integer
d ≥ 2, the strong d-resolving graph GdSR of G has vertex set V (G), and two vertices u, v
S. Klavžar et al.: General d-position sets 41
are adjacent in GdSR if either u, v are MMD in G, or dG(u, v) ≥ d. The terminology used
in this construction comes from the notion of the strong resolving graph introduced in [19]
as a tool to study the strong metric dimension of graphs. See also [15].
The following observation will be useful in the proof of Theorem 5.1.
Observation 1. If G is connected and a vertex u of G is maximally distant from a vertex
v of G, then u ∉ I(v,w) for every w ∈ V (G) ∖ {u}.
Proof. For the sake of contradiction suppose there exists such a vertex w ∈ V (G) ∖ {u}
such that u ∈ I(v,w). Suppose that v = v0 . . . vi−1u = vivi+1 . . . vk = w is a v,w-geodesic.
Since this is a geodesic, it follows that d(v, u) = i. But u is maximally distant from v,
and thus d(v, vi+1) ≤ d(v, u) = i. Now, by following a shortest v, vi+1-path with the path
vi+2 . . . vk = w we arrive at a v,w-path of length less than k, which is a contradiction.
From Observation 1 it follows immediately that if three vertices x, y, z are pairwise
MMD, then x ∉ I(y, z), y ∉ I(x, z), and z ∉ I(x, y). From this we infer that x, y, z lie in
general d-position.
Theorem 5.1. If G is a connected graph and d ≥ 2 is an integer, then gpd(G) ≥ ω(GdSR).
Proof. We consider a set S ⊆ V (GdSR) that induces a (largest) complete subgraph of GdSR.
Then every two vertices x, y ∈ S are MMD in G, or dG(x, y) ≥ d. We now consider three
vertices x, y, z of S in the graph G. If they are pairwise MMD in G, then as above, x, y, z
lie in general d-position. Suppose then that two of them, say x and y, are not MMD in G.
Since x, y are adjacent in GdSR, it follows that dG(x, y) ≥ d. Suppose for instance that x, z
are MMD inG. By Observation 1, it follows that x ∉ I(z, y) and z ∉ I(x, y). If y ∈ I(x, z),
then dG(x, z) = dG(x, y)+dG(y, z) ≥ d+1, and hence x, y, z lie in general d-position. On
the other hand, if y ∉ I(x, z), then by definition, x, y, z lie in general d-position.
It remains only to consider the case in which no pair of x, y, z is MMD in G. This
means that the distance between any two of them is at least d, and this clearly means that
x, y, z are in general d-position.
Note that if d = diam(G), then GdSR is the standard strong resolving graph GSR as
defined in [19]. In this case Theorem 5.1 reduces to gp(G) ≥ ω(GSR), a result earlier
obtained in [12, Theorem 3.1].
Dissociation number and independence number
If G is a graph and S ⊆ V (G), then S is a dissociation set if ⟨S⟩ has maximum degree at
most 1. The dissociation number diss(G) of G is the cardinality of a largest dissociation
set in G. This concept was introduced by Yanakkakis [23]; see also [3, 4, 10]. Further, a
k-path vertex cover of G is a subset S of vertices of G such that every path of order k in
G contains at least one vertex from S. The minimum cardinality of a k-path vertex cover
in G is denoted by ψk(G). The minimum 3-path vertex cover is a dual problem to the
dissociation number because diss(G) = ∣V (G)∣ − ψ3(G); see [10]. For the algorithmic
state of the art on the 3-path vertex cover problem see [2].
Proposition 5.2. IfG is a triangle-free graph, d ≥ 2, and S ⊆ V (G) is a general d-position
set, then S is a dissociation set. Moreover, if d = 2, then S is a general 2-position set if and
only if S is a dissociation set.
42 Ars Math. Contemp. 21 (2021) #P1.03 / 33–44
Proof. Let d be a positive integer such that d ≥ 2. Suppose that S is a general d-position
set in a triangle-free graph G. By Theorem 4.1 every component of the subgraph ⟨S⟩ of G
induced by S is a complete graph. Since G is triangle-free, we conclude that each of these
components has order 1 or 2. Therefore, S is a dissociation set. Now assume that d = 2
and S is a dissociation set in G. The components C1, . . . ,Ck of ⟨S⟩ each have order 1 or 2
and are thus complete graphs. For every pair of distinct indices i, j in [k], the fact that Ci
and Cj are distinct components of the induced subgraph ⟨S⟩ implies that dG(Ci,Cj) ≥ 2.
Therefore, conditions (ii) and (iii) of Theorem 4.1 follow immediately, and hence S is a
general 2-position set.
Proposition 5.2 immediately gives the following result for triangle-free graphs.
Corollary 5.3. If G is a triangle-free graph and d ≥ 2, then gpd(G) ≤ diss(G). Moreover,
gp2(G) = diss(G).
We next relate the particular case of general 2-position number with the independence
number of graphs.
Proposition 5.4. If G is a connected graph without true twins, then gp2(G) ≥ α(G).
Proof. Let x, y ∈ V (G). Suppose first that xy ∈ E(G). Since x and y are not true twins, it
follows that x and y are not MMD. By definition, we infer that xy ∉ E(G2SR). On the other
hand, if xy ∉ E(G), then dG(x, y) ≥ 2 and by definition xy ∈ E(G2SR). Consequently,
G2SR is the complement G of G. Then by using Theorem 5.1, we have gp2(G) ≥ ω(G) =
α(G).
It is straighforward to see that if 2 ≤ m ≤ n, then gp2(Km,n) = n = α(Km,n). Hence
the bound of Proposition 5.4 is sharp. For another such family consider the grid graphs
P2r ◻ P2s. (For the definition of the Cartesian product operation ◻ see, for instance, [9].)
As already mentioned, ψ3(G) = n− diss(G) holds for any graph G of order n. Also, from
[5] it is known that ψ3(P2r ◻ P2s) = 2rs. Moreover, from Corollary 5.3, we have that
gp2(P2r ◻ P2s) = diss(P2r ◻ P2s). Thus,
gp2(P2r ◻ P2s) = diss(P2r ◻ P2s) = 4rs − ψ3(P2r ◻ P2s) = 2rs = α(P2r ◻ P2s) .
6 Infinite graphs and some open problems
The general position problem has been partially studied also on infinite graphs. In [17] it
was proved that gp(P 2∞) = 4, where P 2∞ is the 2-dimensional grid graph (alias the Cartesian
product of two copies of the two way infinite path). The general position number of the 2-
dimensional strong grid graph was also determined, and it was shown that 10 ≤ gp(P 3∞) ≤
16. In [13] the latter lower bound was improved to 14. All these efforts were recently
rounded off in [11] where it is proved that if n ∈ N, then gp(Pn∞) = 22
n−1
. On the other
hand, the following result reduces the study of the general d-position number of infinite
graphs to the case d =∞.
Proposition 6.1. If G is an infinite graph and d <∞, then gpd(G) =∞.
Proof. Let d <∞ be a fixed positive integer. There is nothing to be proved if d = 1, hence
assume that d ≥ 2.
S. Klavžar et al.: General d-position sets 43
Suppose first that diam(G) =∞. In this case G contains an infinite isometric path P =
v1v2 . . .. It is clear that {vdi ∶ i ∈ N} is a general d-position set, and hence gpd(G) =∞.
Suppose second that diam(G) < ∞. Considering an arbitrary vertex of G and its
distance levels we infer that G contains a vertex x with deg(x) = ∞. Let H = ⟨N[x]⟩.
Since H is an infinite graph, Erdős-Dushnik-Miller theorem [7] implies that H contains
a (countably) infinite independent set I or an infinite clique Q (of the same cardinality as
H). If H contains Q, then Q is also a clique of G, and hence G contains an infinite general
d-position set. On the other hand, if H contains I , then I is also an independent set of G.
Moreover, having in mind that H = ⟨N[x]⟩, we infer that each pair of vertices of I is at
distance 2 in G. This fact in turn implies that I is an infinite general d-position set of G.
We conclude that gpd(G) =∞.
6.1 Open questions
In this section we point out several questions that, in our opinion, are worthy of considera-
tion.
• In [20, Lemma 5.1] there is a polynomial algorithm for the dissociation number
of trees T and hence for gp2(T ). On the other hand, gpdiam(T )(T ) can also be
efficiently computed. Hence, is it possible to compute in polynomial time gpd(T )
for any 2 < d < diam(T )? More generally, what can be done for the case of block
graphs? We know that the simplicial vertices of a block graph form a gp-set. Can the
algorithm of Papadimitriou and Yannakakis be modified for block graphs?
• Compare diss(G) with gp2(G) for graphs G with ω(G) ≥ 3. Our guess is that these
invariants are incomparable in such graphs. Is there some relationship when G is a
block graph?
• What is gpd(G) whenever G is a grid-like graph? Note that by applying Corol-
lary 5.3 together with Theorem 4.1 in [5], one can find the value of gp2(Pn ◻ Pm)
for any n and m. Find gpd(Pn ◻ Pm) for d ≥ 3. Find the general d-position number
of a partial grid graph for d ≥ 2.
ORCID iDs
Sandi Klavžar https://orcid.org/0000-0002-1556-4744
Douglas F. Rall https://orcid.org/0000-0002-5482-756X
Ismael G. Yero https://orcid.org/0000-0002-1619-1572
References
[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, doi:10.1016/j.amc.2019.04.064.
[2] Z. Bai, J. Tu and Y. Shi, An improved algorithm for the vertex cover P3 problem on graphs
of bounded treewidth, Discrete Math. Theor. Comput. Sci. 21 (2019), Paper No. 17, 13, doi:
10.23638/dmtcs-21-4-17.
[3] R. Boliac, K. Cameron and V. V. Lozin, On computing the dissociation number and the induced
matching number of bipartite graphs, Ars Combin. 72 (2004), 241–253.
44 Ars Math. Contemp. 21 (2021) #P1.03 / 33–44
[4] B. Brešar, B. L. Hartnell and D. F. Rall, Uniformly dissociated graphs, Ars Math. Contemp. 13
(2017), 293–306, doi:10.26493/1855-3974.1013.46a.
[5] B. Brešar, M. Jakovac, J. Katrenič, G. Semanišin and A. Taranenko, On the vertex k-path cover,
Discrete Appl. Math. 161 (2013), 1943–1949, doi:10.1016/j.dam.2013.02.024.
[6] S. U. Chandran and G. J. Parthasarathy, The geodesic irredundant sets in graphs, International
J.Math. Combin. 4 (2016), 135–143, doi:10.5281/zenodo.826833.
[7] B. Dushnik and E. W. Miller, Partially ordered sets, Amer. J. Math. 63 (1941), 600–610, doi:
10.2307/2371374.
[8] M. Ghorbani, H. R. Maimani, M. Momeni, F. Rahimi 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, doi:10.7151/dmgt.2269.
[9] W. Imrich, S. Klavžar and D. F. Rall, Topics in Graph Theory: Graphs and Their Cartesian
Product, A K Peters, Ltd., Wellesley, MA, 2008, http://math.furman.edu/˜drall/
TGT/book.html.
[10] F. Kardoš, J. Katrenič and I. Schiermeyer, On computing the minimum 3-path vertex cover and
dissociation number of graphs, Theoret. Comput. Sci. 412 (2011), 7009–7017, doi:10.1016/j.
tcs.2011.09.009.
[11] S. Klavžar and G. Rus, The general position number of integer lattices, Appl. Math. Comput.
390 (2021), Paper No. 125664, 4, doi:10.1016/j.amc.2020.125664.
[12] S. Klavžar and I. G. Yero, The general position problem and strong resolving graphs, Open
Math. 17 (2019), 1126–1135, doi:10.1515/math-2019-0088.
[13] S. Klavžar, B. Patkós, G. Rus and I. G. Yero, On general position sets in Cartesian products,
Results Math. 76 (2021), Paper No. 123, 21, doi:10.1007/s00025-021-01438-x.
[14] J. Körner, On the extremal combinatorics of the Hamming space, J. Combin. Theory Ser. A 71
(1995), 112–126, doi:10.1016/0097-3165(95)90019-5.
[15] D. Kuziak, M. L. Puertas, J. A. Rodrı́guez-Velázquez and I. G. Yero, Strong resolving graphs:
the realization and the characterization problems, Discrete Appl. Math. 236 (2018), 270–287,
doi:10.1016/j.dam.2017.11.013.
[16] P. Manuel and S. Klavžar, A general position problem in graph theory, Bull. Aust. Math. Soc.
98 (2018), 177–187, doi:10.1017/s0004972718000473.
[17] P. Manuel and S. Klavžar, The graph theory general position problem on some interconnection
networks, Fund. Inform. 163 (2018), 339–350, doi:10.3233/fi-2018-1748.
[18] P. K. Neethu, S. V. U. Chandran, M. Changat and S. Klavžar, On the general position number
of complementary prisms, Fundam. Inform 178 (2021), 267–281, doi:10.3233/fi-2021-2006.
[19] O. R. Oellermann and J. Peters-Fransen, The strong metric dimension of graphs and digraphs,
Discrete Appl. Math. 155 (2007), 356–364, doi:10.1016/j.dam.2006.06.009.
[20] C. H. Papadimitriou and M. Yannakakis, The complexity of restricted spanning tree problems,
J. Assoc. Comput. Mach. 29 (1982), 285–309, doi:10.1145/322307.322309.
[21] B. Patkós, On the general position problem on Kneser graphs, Ars Math. Contemp. 18 (2020),
273–280, doi:10.26493/1855-3974.1957.a0f.
[22] 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, doi:10.1017/s0004972720001276.
[23] M. Yannakakis, Node-deletion problems on bipartite graphs, SIAM J. Comput. 10 (1981), 310–
327, doi:10.1137/0210022.