ISSN 2590-9770
The Art of Discrete and Applied Mathematics 8 (2025) #P1.02
https://doi.org/10.26493/2590-9770.1745.5f4
(Also available at http://adam-journal.eu)
Generalization of edge general position problem*
Paul Manuel
Department of Information Science, College of Life Science, Kuwait University, Kuwait
R. Prabha
Department of Mathematics, Ethiraj College for Women, Chennai, Tamilnadu, India
Sandi Klavžar†
Faculty of Mathematics and Physics, University of Ljubljana, Slovenia and
Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia and
Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia
Dedicated to Dragan Marušič on the occasion of his 70th birthday.
Received 18 December 2023, accepted 27 January 2024, published online 20 February 2025
Abstract
The edge geodesic cover problem of a graph G is to find a smallest number of geodesics
that cover the edge set of G. The edge k-general position problem is introduced as the
problem to find a largest set S of edges of G such that at most k − 1 edges of S lie on
a common geodesic. We show that these are dual min-max problems and connect them
to an edge geodesic partition problem. Using these connections, exact values of the edge
k-general position number is determined for different values of k and for various networks
including torus networks, hypercubes, and Benes networks.
Keywords: General position set, edge geodesic cover problem, edge k-general position problem,
torus network, hypercube, Benes network.
Math. Subj. Class.: 05C12, 05C76
*We thank the reviewer for a very careful reading of the article. This work was supported and funded by
Kuwait University, Kuwait and the Research Project No. is FI 02/21.
†Corresponding author.
E-mail addresses: pauldmanuel@gmail.com (Paul Manuel), prabha75@gmail.com (R. Prabha),
sandi.klavzar@fmf.uni-lj.si (Sandi Klavžar)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Art Discrete Appl. Math. 8 (2025) #P1.02
1 Introduction
Dual min-max invariant combinatorial problems are central topics in graph theory and more
generally in combinatorics, cf. [2]. Here we consider an instance of such dual problems,
the edge geodesic cover problem and the edge general position problem, where we will use
the first as a tool to study the second.
An edge geodesic cover of G is a set S of geodesics such that each edge of G belongs
to at least one geodesic of S. The edge geodesic cover number of G, gcovere(G), is the
minimum cardinality of an edge geodesic cover of G. The edge geodesic cover problem
is to find a minimum cardinality edge geodesic cover of G, cf. [19]. An edge geodesic
partition of G is a set S of geodesics such that each edge of G belongs to exactly one
geodesic of S. The edge geodesic partition number of G, gparte(G), is the minimum
cardinality of an edge geodesic partition of G. The edge geodesic partition problem is to
find a minimum cardinality edge geodesic partition of G. A survey on edge geodesic cover
and partition problems up to 2018 can be found in [19].
For k ≥ 3, we introduce the edge k-general position sets as follows. An edge k-general
position set is a set S of edges of G such that no k edges of S lie on a common geodesic,
that is, |S ∩ E(P )| ≤ k − 1 for any geodesic P of G. An edge k-general position set
of maximum cardinality in G is called an edge k-gp set. Its cardinality is denoted by
k-gpe(G) and called the edge k-gp number. The edge k-general position problem is to
find an edge k-gp set. The edge 3-general position problem is known as the edge general
position problem and was studied for the first time in [23] and then continued in [13, 14].
The corresponding invariant is called the gpe-number of G and denoted by gpe(G). The
related (vertex) general position problem, which was independently introduced in [3, 22],
has already been extensively studied, see [1, 5, 10–12, 16, 28, 30, 31, 33].
The main objective of this paper is to demonstrate that the edge geodesic cover prob-
lem and the edge k-general position problem form a pair of dual min-max combinatorial
problems. To do so, we first establish some basic results in Section 2. The advantage
of dual min-max invariant combinatorial problems is that one problem can be solved by
means of the other problem. In this paper we apply this approach to the above-mentioned
problems. In Section 3 we determine the edge k-gp number for torus graphs C2r □C2r
and k = 2t + 1. Then, in Section 4, we demonstrate that partial cubes contain large edge
k-gp sets and prove that the edge k-gp number of a hypercube Qd is (k − 1)2d−1. In Sec-
tion 5 we solve the edge k-gp problem for Benes networks for k ∈ {3, 5}. In the rest of the
introduction, we give some further definitions needed.
Let Pn denote the path on n vertices and Cn the cycle on n vertices. The distance
dG(u, v) between vertices u and v of G is the number of edges on a shortest u, v-path.
Shortest paths are also known as isometric paths or geodesics. The diameter diam(G)
of G is the maximum distance between vertices of G. A diametral path is an isomet-
ric path whose length is equal to the diameter of G. If X,Y ⊆ V (G), then dG(X,Y ) =
minx∈X,y∈Y dG(x, y). If H and H ′ are subgraphs of G, then dG(H,H ′) =
dG(V (H), V (H
′)). In this manner, if e, f ∈ E(G), then dG(e, f) is the minimum dis-
tance between a vertex of e and a vertex of f .
2 A few preliminary results
In this section we present some preliminary results on edge k-general position sets. We
first show that if the diameter of a graph is at most 2k− 2, then the matching of cardinality
P. Manuel et al.: Generalization of edge general position problem 3
k of the graph are edge k-general position sets. (Recall that a matching of G is a set of
independent edges of G.)
Proposition 2.1. Let G be a graph and k ≥ 3. Then diam(G) ≤ 2k − 2 if and only if
every matching of size k is an edge k-general position set.
Proof. Suppose that diam(G) ≤ 2k − 2. Let M be an arbitrary matching of G of order k
and assume that the edges from M lie on a common geodesic P . Since M is a matching,
the length of P is at least 2k−1 and so diam(G) ≥ 2k−1 would hold. As this contradicts
our assumption we get that M is an edge k-general position set.
Conversely, suppose that every matching of order k is an edge k-general position set.
Assume on the contrary that diam(G) ≥ 2k−1 and let P be a geodesic of length diam(G).
Selecting every second edge of P we construct a matching M of order at least k. Let M ′
be a subset of M with |M ′| = k. As M ′ is a matching, by our assumption we have that
M ′ is an edge k-general position set, but this is not the case as all the edges from M ′ lie on
P .
A j-geodesic is a geodesic of length j. The following proposition is a useful tool to
prove that a given set of edges is an edge general position set.
Proposition 2.2. Let S be a set of edge-disjoint geodesics in G each of length j and let
ℓ = minP,Q∈S dG(P,Q). If k ≥ 2 and dG(P,Q) < ℓ(k − 1) + j(k − 2) holds for every
P,Q ∈ S such that P and Q lie in a common geodesic, then no k paths from S lie on a
common geodesic.
Proof. Suppose on the contrary that the paths P1, . . . , Pk from S lie (in this order) on a
common geodesic. Then
dG(P1, Pk) =
k−2∑
i=1
(dG(Pi, Pi+1) + j) + dG(Pk−1, Pk)
=
k−1∑
i=1
dG(Pi, Pi+1) + j(k − 2)
≥ ℓ(k − 1) + j(k − 2),
a contradiction since P1 and Pk lie on a common geodesic and we have assumed that then
dG(P1, Pk) < ℓ(k − 1) + j(k − 2) holds.
Setting j = 1 in Proposition 2.2 we have the following consequence.
Corollary 2.3. Let S ⊆ E(G), ℓ = mine,f∈S dG(e, f), and L = maxe,f∈S dG(e, f). If
L < ℓ(k − 1) + (k − 2), then S is an edge k-general position set.
We conclude the section by the following simple, yet fundamental inequalities com-
paring gpe(G), gcovere(G), and gparte(G). The result establishes how the edge geodesic
cover problem and the edge general position problem constitute dual min-max combinato-
rial problems.
Lemma 2.4. If G is a graph and k ≥ 3, then
k-gpe(G) ≤ (k − 1) · gcovere(G) ≤ (k − 1) · gparte(G) .
4 Art Discrete Appl. Math. 8 (2025) #P1.02
Proof. Each geodesic from a geodesic cover can contain at most k− 1 edges from an edge
k-general position set. Hence the left inequality. The right inequality follows because a
geodesic partition is a geodesic cover, cf. [19].
3 The edge k-gp problem for torus
The Cartesian product G□H of graphs G and H is defined on the vertex set V (G□H) =
V (G) × V (H), vertices (g, h) and (g′, h′) are adjacent if either gg′ ∈ E(G) and h = h′,
or g = g′ and hh′ ∈ E(H). See the book [8] for more information on this graph operation.
Cartesian products of cycles Cn □Cm are known as torus graphs. As in this paper we
will consider only these products, we simplify the general terminology for products as
follows. Two edges x = (x1, x2) and y = (y1, y2) of a torus are said to be parallel if
d(x1, y2) = d(x2, y1) = d(x1, y1) + 1 = d(x2, y2) + 1. The edges of Cn □Cm that
project on the edges of the first factor will be called horizontal edges, while the edges that
project on Cm are vertical edges. Analogously we will speak of horizontal cycles (copies
of Cn in the product) and of vertical cycles.
Lemma 3.1. If r ≥ 3 and 2t ≤ 2r−1 − 2, then
(2t + 1)-gpe(C2r ) = 2t+1 .
Proof. Set k = 2t + 1. Since gcovere(C2r ) = gparte(C2r ) = 2, Lemma 2.4 implies that
it is enough to show that k-gpe(C2r ) ≥ 2(k − 1). That is, we need to construct an edge
k-general position set S of C2r with |S| = 2k− 2 = 2t+1. We proceed to construct such a
set S.
Let V (C2r ) = {v1, v2, . . . , v2r}. Define S to be the set containing edges ei = uivi,
i ∈ [2t+1], where the edges are equidistant on C2r , that is, we select them such that
dC2r (ei, ei+1) = 2
r−t−1 − 1
holds for all i ∈ [2t+1 − 1], cf. Figure 1.
Figure 1: The edges e1, e2 · · · e2t+1 of S′ lie on geodesic P . The end-vertices of the edge
ei are ui and vi, such that u1, v1, u2, v2, . . . , u2t+1, v2t+1 are in increasing order. We have
d(ei, ei+1) = 2
r−t−1 − 1.
We claim that S is an edge k-general position set. If not, then there exists a subset S′
of S such that |S′| = k = 2t + 1 and the edges of S′ lie on a common geodesic P . By
the equidistant distribution of the edges from S we may without loss of generality assume
that S′ = {e1, e2, . . . , e2t+1}. As P is a geodesic which contains 2t + 1 edges with the
distance 2r−t−1 − 1 between the consecutive edges, we have
dC2r (u1, v2t+1) = (2
t + 1) + 2t(2r−t−1 − 1) = 2r−1 + 1 ,
a contradiction because diam(C2r−1) = 2r−1.
P. Manuel et al.: Generalization of edge general position problem 5
Note that Lemma 3.1 provides an example where both inequalities of Lemma 2.4 are
attained.
Figure 2: v1, . . . , v8 are diagonal vertices of C8 □C8. The vertex v5 is the red bullet. There
are two red lines. One is red solid line and the other is red dotted line. Both geodesics (the
red solid line and the red dotted line) are diametral paths such that v5 is the mid point of
both geodesics. The pairs of diametral paths at v1, . . . , v8 partition E(G).
Proposition 3.2. If r ≥ 2, then gcovere(C2r □C2r) = gparte(C2r □C2r) = 4r.
Proof. Set G = C2r □C2r.
Since gcovere(G) ≥ ⌈|E(G)|/diam(G)⌉ (cf. [20]), diam(G) = 2r, and |E(G)| =
2 · 2r · 2r, we infer that gcovere(G) ≥ 4r.
To prove that gcovere(G) ≤ 4r we proceed by construction. Let v1, . . . , v2r be the
diagonal vertices of G as demonstrated in Figure 2. For each diagonal vertex vi let P ′vi
and P ′′vi be two edge disjoint diametral paths as shown in Figure 2 for the vertices v5, v6,
and v7. Then vi is the midpoint of P ′vi and P
′′
vi which is possible because both factors of
G are even paths. The set of paths {P ′vi , P
′′
vi : i ∈ [2r]} then partitions E(G). Thus,
gcovere(G) ≤ gparte(G) ≤ 4r.
Theorem 3.3. If r ≥ 3 and 2t ≤ 2r−1 − 2, then
(2t + 1)-gpe(C2r □C2r ) = 2r+t+1 .
Proof. The technique of the proof is parallel to the one from the proof of Lemma 3.1. More
precisely, we set k = 2t + 1 and are going to construct an edge k-general position set S of
G with |S| = (k − 1) · gparte(G) = 2t · 2r+1 = 2r+t+1.
Consider a horizontal cycle of C2r □C2r , say Ch. Using Lemma 3.1, construct a set
Sh of edges from Ch of cardinality 2t which contains equidistant edges eh1 , e
h
2 , . . ., e
h
2t of
the cycle, that is, d(ehi , e
h
i+1) = d(e
h
j , e
h
j+1) = 2
r−t+1 − 1 for 1 ≤ i, j ≤ 2t. Now add all
6 Art Discrete Appl. Math. 8 (2025) #P1.02
Figure 3: There are two type of edges: red dotted edges and blue dotted edges. The blue
dotted edges are vertical and the red dotted edges are horizontal. (a) The red dotted edges
and the blue dotted edges form an edge 3-general position set of the 8 × 8 torus. (b) The
red dotted edges and the blue dotted edges form an edge 5-general position set of the 8× 8
torus.
the edges of Sh to S. Further, add to S all the edges parallel to the edges from Sh. See
Figure 3 where the edges from S are the red dotted edges. At this stage we have added to
|S| precisely 2t · 2r = 2r+t edges because there are 2r parallel edges for every given edge
in C2r □C2r . We proceed analogously for the vertical cycles of C2r □C2r . That is, we
select one such cycle, select in it 2t equidistant edges at the distance 2r−t+1 − 1, and add
to S all these edges as well as all the edges parallel to them. At this stage, the cardinality
of S is doubled and thus we have ended up with |S| = 2r+t+1.
We claim that the above constructed S is an edge k-general position set of C2r □C2r . If
this is not the case, then there exists a subset R of S with |R| = 2t+1 such that all the edges
of R lie on a common geodesic P . Since no two parallel edges of a torus lie on a geodesic,
we infer that R does not contain any parallel edges. Without loss of generality we may
assume that R has at least as many horizontal edges as vertical edges. Since |R| = 2t + 1,
this means that R contains at least 2t−1 + 1 horizontal edges. Let Rh denote the set of
all those horizontal edges, Rh = {eh1 , eh2 , . . . , ehs}, where we know that s ≥ 2t−1 + 1.
Set ehi = uivi and assume without loss of generality that u1, v1, u2, v2, . . . , us, vs are in
a non-decreasing order (The meaning of non-decreasing order is explained in Figure 1).
Such an order is possible as no two edges from Rh are parallel. The situation is illustrated
in Figure 4.
Figure 4: Rh = {eh1 , eh2 , . . . , ehs}. The vertices u1, v1, u2, v2, . . . , us, vs are in increasing
order. Also, d(ehi , e
h
i+1) ≥ 2r−t+1 − 1.
P. Manuel et al.: Generalization of edge general position problem 7
Consider now the distance d(u1, vs) (along the geodesic P ). We have
d(u1, vs) = (1 + d(e
h
1 , e
h
2 )) + (1 + d(e
h
2 , e
h
3 )) + · · ·+ (1 + d(ehs−1, ehs )) + 1
≥ (1 + 2r−t+1 − 1) + (1 + 2r−t+1 − 1) + · · ·+ (1 + 2r−t+1 − 1) + 1
= (s− 1) · 2r−t+1 + 1
≥ 2t−1 · 2r−t+1 + 1
≥ 2r + 1.
This leads to a contradiction because the length of the geodesic P in C2r □C2r is greater
as diam(C2r □C2r) = 2r. This proves the claim and hence the theorem.
In addition to the Cartesian product of two cycles, it would certainly be interesting to
consider the Cartesian product of a cycle by a path and the Cartesian product of a path by
a path. However, it seems that this would require a different approach to the one we have
used for the torus graphs.
4 The edge k-gp problem for partial cubes
In this section we extend results on gpe(G) of a partial cube G from [23] to k-gpe(G). For
this sake, we first recall the concept needed.
A graph G is a partial cube if G is a subgraph of some hypercube Qd such that if
x, y ∈ V (G), then dG(x, y) = dQd(x, y). Papers [4, 25, 26, 29] present a selection of
recent developments on partial cubes. Edges xy and uv of a graph G are in relation Θ
if dG(x, u) + dG(y, v) ̸= dG(x, v) + dG(y, u). A connected graph G is a partial cube if
and only if G is bipartite and Θ is transitive [32]. As Θ is reflexive and symmetric on an
arbitrary graph, it partitions the edge set of a partial cube into Θ-classes.
Lemma 4.1. Let G be a partial cube, k ≥ 3, and F1, . . . , Fk−1 be Θ-classes of G. Then⋃k−1
i=1 Fi is an edge k-gp set of G.
Proof. Consider an arbitrary set X of k edges from
⋃k−1
i=1 Fi. Then by the pigeonhole
principle at least two of the edges from X lie in a common Θ-class Fi. As no two edges
from Fi lie on a common geodesic, cf. [6, Lemma 11.1] we get that the edges from X do
not lie on a common geodesic. We conclude that X is an edge k-gp set of G.
Lemma 4.1 enables us to find large edge k-gp sets in partial cubes. We demonstrate
this claim by the following result for hypercubes. Recall that the d-dimensional hypercube
Qd, d ≥ 1, is a graph with V (Qd) = {0, 1}r, and there is an edge between two vertices if
and only if they differ in exactly one coordinate.
Theorem 4.2. If 3 ≤ k ≤ d+ 1, then
k-gpe(Qd) = (k − 1)2d−1 = (k − 1)gcovere(Qd) = (k − 1)gparte(Qd) .
Proof. It is well-known that Qd is a partial cube and that it has Θ-classes Fi, i ∈ [d],
where Fi is formed by the edges whose endpoints differ in coordinate i, cf. [6–8]. Note
that |Fi| = 2d−1. Then Lemma 4.1 implies that k-gpe(Qr) ≥ (k − 1)2d−1. As we have
assumed that k ≤ d+ 1 and Qd contains d2d−1 edges, this is indeed possible.
8 Art Discrete Appl. Math. 8 (2025) #P1.02
To prove the reverse inequality we recall from the proof of [23, Theorem 3.2] that Qd
admits an isometric path edge partition consisting of 2d−1 paths. Lemma 2.4 thus implies
that
(k − 1) · 2d−1 ≤ k-gpe(Qd) ≤ (k − 1) · gparte(Qd) ≤ (k − 1) · 2d−1 ,
hence applying Lemma 2.4 again we have equality everywhere in it for Qd.
5 The edge k-gp problem for Benes networks
Benes networks were presented in [21] and have been studied subsequently in different
contexts, see for instance [7, 9, 15, 17, 27]. For r ≥ 3, the r-dimensional Benes network
BN(r) is defined as follows. The vertex set consists of all ordered pairs [s, i], where s
runs over all r-bit binary strings and i ∈ {0, 1, . . . , 2r}. In the normal representation
of BF (r), the first coordinate of the vertex is interpreted as the row of the vertex and
its second coordinate is a column called the level of the vertex. The vertices [s, i] and
[s′, i′], where i, i′ ≤ r, are adjacent if |i − i′| = 1, and either s = s′ or s and s′ differ
precisely in the ith bit. When i, i′ ≥ r the edges are vertically reflected (in the normal
representation). The edges between level i − 1 and level i are called level i edges for
1 ≤ i ≤ 2r. The formal definition should be clear from Figure 5, where BN(3) is shown
in its normal representation. Clearly, BN(r) has (2r + 1)2r vertices.
Figure 5: The Benes network BN(3) consists of back-to-back butterflies and is an edge
disjoint union of two butterflies.
Theorem 5.1. If r ≥ 3, then
gcovere(BN(r)) = gparte(BN(r)) = 2
r+1 .
P. Manuel et al.: Generalization of edge general position problem 9
Proof. An alternative way to represent Benes networks is that BN(r) consists of two back-
to-back butterflies BF(r), cf. [18, 21, 24], that is, of two copies of BF(r) sharing level r
vertices. It is known that diam(BN(r)) = diam(BF(r)) = 2r, cf. [18,21,24], and that the
edge set of BF(r) can be partitioned with respect to 2r diametral paths [21]. It follows that
the edge set of BN(r) can be partitioned with respect to 2r+1 diametral paths of BN(r).
Consequently, Lemma 2.4 implies gcovere(BN(r)) ≤ gparte(BN(r)) ≤ 2r+1 .
To prove the reverse inequality, consider the set S of edges which are incident to the
vertices of level 0, level r, and level 2r. Then |S| = 2 · 2r +4 · 2r +2 · 2r = 2r+3. Since a
geodesic can cover a maximum of four edges of S [21], at least 2r+3/4 = 2r+1 geodesics
are required to cover all the edges of S. Hence, gcovere(BN(r)) ≥ 2r+3/4 = 2r+1. Thus,
gparte(BN(r)) ≥ gcovere(BN(r)) ≥ 2r+1.
Theorem 5.2. If k ∈ {3, 5}, then
k-gpe(BN(r)) = (k − 1) · 2r+1 .
Proof. By combining Lemma 2.4 with Theorem 5.1, it is enough to identify an edge general
position set S of cardinality 2r+2 for k = 3, and an edge 5-general position set S′ of
cardinality 2r+3 for k = 5.
For k = 3, consider the set S of edges in BN(r) which are incident to the degree two
vertices (in levels 0 and 2r). Since each level consists of 2r vertices and each vertex at
level 0 and level 2r is of degree two, |S| = 2r+2. An arbitrary geodesic contains at most
two edges of S, cf. [21]. Thus, S is an edge general position set of BN(r) of the required
cardinality.
For k = 5, consider the set of edges S′ which are incident to the vertices of level 0,
level r, and level 2r. Then, as already noticed in the proof of Theorem 5.1, |S′| = 2r+3.
As a geodesic contains at most four edges of S′, we conclude that S is an edge general
position set of BN(r) of the required cardinality.
6 Conclusion
In this paper, we have demonstrated that the edge geodesic cover problem and the edge
k-general position problem form a pair of dual min-max invariant combinatorial problems.
We have solved the edge k-general position problem completely for hypercubes and for
certain cases of torus. In addition, we have solved the edge k-general position problem
for Benes networks BN(3) and BN(5). The edge geodesic cover problem and the edge
geodesic partition problem are completely solved for hypercubes, torus and Benes net-
works. Studying the interplay between these two concepts seems to be an interesting topic.
Among other things, it would be interesting to explore these dual min-max invariant combi-
natorial problems for intersection graphs, subclasses of perfect graphs, and different Cayley
graphs.
ORCID iDs
Paul Manuel https://orcid.org/0000-0002-1125-6066
R. Prabha https://orcid.org/0009-0000-3824-3137
Sandi Klavžar https://orcid.org/0000-0002-1556-4744
10 Art Discrete Appl. Math. 8 (2025) #P1.02
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. Com-
put. 359 (2019), 84–89, doi:10.1016/j.amc.2019.04.064, https://doi.org/10.1016/
j.amc.2019.04.064.
[2] Y. Azar, N. Buchbinder, T.-H. H. Chan, S. Chen, I. Cohen, A. Gupta, Z. Huang, N. Kang,
V. Nagarajan, J. Naor and D. Panigrahi, Online algorithms for covering and packing prob-
lems with convex objectives, in: 57th Annual IEEE Symposium on Foundations of Computer
Science—FOCS 2016, IEEE Computer Soc., Los Alamitos, CA, pp. 148–157, 2016, doi:
10.1109/FOCS.2016.24, https://doi.org/10.1109/FOCS.2016.24.
[3] U. Chandran S.V. and G. Jaya Parthasarathy, The geodesic irredundant sets in graphs, Int. J.
Math. Comb. 4 (2016), 135–143.
[4] V. Chepoi, K. Knauer and T. Marc, Hypercellular graphs: partial cubes without Q−3 as par-
tial cube minor, Discrete Math. 343 (2020), 111678, 28 pp., doi:10.1016/j.disc.2019.111678,
https://doi.org/10.1016/j.disc.2019.111678.
[5] G. Di Stefano, S. Klavžar, A. Krishnakumar, J. Tuite and I. G. Yero, Lower general position sets
in graphs, 2024, arXiv:2306.09965 [math.CO], to appear in Discuss. Math. Graph
Theory.
[6] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, Discrete Mathematics
and its Applications, CRC Press, Boca Raton, FL, 2nd edition, 2011, doi:10.1201/b10959,
https://doi.org/10.1201/b10959.
[7] L.-H. Hsu and C.-K. Lin, Graph Theory and Interconnection Networks, CRC Press,
Boca Raton, FL, 2008, doi:10.1201/9781420044829, https://doi.org/10.1201/
9781420044829.
[8] 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.
[9] A. Karimi, K. Aghakhani, S. E. Manavi, F. Zarafshan and S. A. R. Al-Haddad, Introduction and
analysis of optimal routing algorithm in Benes networks, Procedia Comp. Sci. 42 (2014), 313–
319, doi:10.1016/j.procs.2014.11.068, https://doi.org/10.1016/j.procs.2014.
11.068.
[10] S. Klavžar, A. Krishnakumar, J. Tuite and I. G. Yero, Traversing a graph in general position,
Bull. Aust. Math. Soc. 108 (2023), 353–365, doi:10.1017/s0004972723000102, https://
doi.org/10.1017/s0004972723000102.
[11] S. Klavžar, P. K. Neethu and U. Chandran S. V., The general position achievement game
played on graphs, Discrete Appl. Math. 317 (2022), 109–116, doi:10.1016/j.dam.2022.04.019,
https://doi.org/10.1016/j.dam.2022.04.019.
[12] S. Klavžar and G. Rus, The general position number of integer lattices, Appl. Math. Comput.
390 (2021), Paper No. 125664, 4 pp., doi:10.1016/j.amc.2020.125664, https://doi.org/
10.1016/j.amc.2020.125664.
[13] S. Klavžar and E. Tan, Edge general position sets in Fibonacci and Lucas cubes, Bull. Malays.
Math. Sci. Soc. 46 (2023), Paper No. 120, 11 pp., doi:10.1007/s40840-023-01517-y, https:
//doi.org/10.1007/s40840-023-01517-y.
[14] S. Klavžar, E. Tan and J. Tian, Extremal edge general position sets in some graphs, Graphs
Comb. 40 (2024), Paper No. 40, 11 pp., doi:10.1007/s00373-024-02770-z, https://doi.
org/10.1007/s00373-024-02770-z.
P. Manuel et al.: Generalization of edge general position problem 11
[15] P. Kolman, On nonblocking properties of the Beneš network, in: Algorithms—ESA ’98
(Venice), Springer, Berlin, Heidelberg, volume 1461 of Lecture Notes in Comput. Sci.,
pp. 259–270, 1998, doi:10.1007/3-540-68530-8\_22, https://doi.org/10.1007/
3-540-68530-8_22.
[16] D. Korže and A. Vesel, General position sets in two families of Cartesian product graphs,
Mediterr. J. Math. 20 (2023), Paper No. 203, 12 pp., doi:10.1007/s00009-023-02416-z,
https://doi.org/10.1007/s00009-023-02416-z.
[17] F. T. Leighton, Introduction to Parallel Algorithms and Architectures. Arrays, Trees, Hyper-
cubes, Morgan Kaufmann, San Mateo, CA, 1992, doi:10.1016/C2013-0-08299-0, https:
//doi.org/10.1016/C2013-0-08299-0.
[18] F. T. Leighton, B. M. Maggs and R. K. Sitaraman, On the fault tolerance of some
popular bounded-degree networks, SIAM J. Comput. 27 (1998), 1303–1333, doi:10.1137/
S0097539793255163, https://doi.org/10.1137/S0097539793255163.
[19] P. Manuel, Revisiting path-type covering and partitioning problems, 2018,
arXiv:1807.10613 [math.CO].
[20] P. Manuel, On the isometric path partition problem, Discuss. Math. Graph Theory 41 (2021),
1077–1089, doi:10.7151/dmgt.2236, https://doi.org/10.7151/dmgt.2236.
[21] P. Manuel, M. I. Abd-El-Barr, I. Rajasingh and B. Rajan, An efficient representation of Benes
networks and its applications, J. Discrete Algorithms 6 (2008), 11–19, doi:10.1016/j.jda.2006.
08.003, https://doi.org/10.1016/j.jda.2006.08.003.
[22] 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, https://doi.org/10.1017/
S0004972718000473.
[23] P. Manuel, R. Prabha and S. Klavžar, The edge general position problem, Bull. Malays. Math.
Sci. Soc. 45 (2022), 2997–3009, doi:10.1007/s40840-022-01319-8, https://doi.org/
10.1007/s40840-022-01319-8.
[24] P. Manuel, K. Qureshi, A. William and A. Muthumalai, VLSI layout of Benes networks,
J. Discrete Math. Sci. Cryptogr. 10 (2007), 461–472, doi:10.1080/09720529.2007.10698132,
https://doi.org/10.1080/09720529.2007.10698132.
[25] T. Marc, Classification of vertex-transitive cubic partial cubes, J. Graph Theory 86 (2017),
406–421, doi:10.1002/jgt.22134, https://doi.org/10.1002/jgt.22134.
[26] A. Mofidi, On partial cubes, well-graded families and their duals with some applications in
graphs, Discrete Appl. Math. 283 (2020), 207–230, doi:10.1016/j.dam.2020.01.013, https:
//doi.org/10.1016/j.dam.2020.01.013.
[27] M. Numan, N. Naz and F. Uddin, New results on topological indices for Benes and butterfly
networks, U.P.B. Sci. Bull. Ser. A: Appl. Math. Phys. 82 (2020), 33–42.
[28] 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, https://doi.org/10.26493/
1855-3974.1957.a0f.
[29] N. Polat, On antipodal and diametrical partial cubes, Discuss. Math. Graph Theory 41 (2021),
1127–1145, doi:10.7151/dmgt.2305, https://doi.org/10.7151/dmgt.2305.
[30] J. Tian and K. Xu, The general position number of Cartesian products involving a factor with
small diameter, Appl. Math. Comput. 403 (2021), Paper No. 126206, 10 pp., doi:10.1016/j.amc.
2021.126206, https://doi.org/10.1016/j.amc.2021.126206.
[31] J. Tian, K. Xu and D. Chao, On the general position numbers of maximal outerplane
graphs, Bull. Malays. Math. Sci. Soc. 46 (2023), Paper No. 198, 14 pp., doi:10.1007/
s40840-023-01592-1, https://doi.org/10.1007/s40840-023-01592-1.
12 Art Discrete Appl. Math. 8 (2025) #P1.02
[32] P. M. Winkler, Isometric embedding in products of complete graphs, Discrete Appl. Math.
7 (1984), 221–225, doi:10.1016/0166-218X(84)90069-6, https://doi.org/10.1016/
0166-218X(84)90069-6.
[33] Y. Yao, M. He and S. Ji, On the general position number of two classes of graphs,
Open Math. 20 (2022), 1021–1029, doi:10.1515/math-2022-0444, https://doi.org/
10.1515/math-2022-0444.