pith. sign in

arxiv: 2604.15909 · v1 · submitted 2026-04-17 · 🧮 math.CO

The general position number of digraphs

Ullas Chandran S.V. , Gabriele Di Stefano , Grahame Erskine , Haritha S , Elias John Thomas , James Tuite This is my paper

Pith reviewed 2026-05-10 08:29 UTC · model grok-4.3

classification 🧮 math.CO
keywords general position numberdigraphsoriented graphsNP-completenesscirculant digraphsKautz digraphspermutation digraphsshortest paths
0
0 comments X

The pith

The general position number of a digraph is the size of the largest vertex set with no three vertices on a common shortest directed path, and finding it is NP-complete for oriented graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper extends the general position number from undirected graphs to digraphs by defining it as the largest subset of vertices such that no three lie on a single shortest directed path. The authors establish bounds on this number for general digraphs and prove that computing it is NP-complete even when restricted to oriented graphs. They derive exact values or tight bounds for important families including circulant digraphs, Kautz digraphs, and permutation digraphs. The work also examines how the general position number varies across different orientations of the same underlying undirected graph.

Core claim

We define the general position number gp(D) of a digraph D as the maximum cardinality of a vertex set S in which no three vertices are contained in a common shortest directed path. We prove that the problem of computing gp(D) is NP-complete for oriented graphs. For several structured families of digraphs we obtain closed-form expressions or sharp bounds, and we relate the values obtained from different orientations of an undirected graph.

What carries the argument

The general position number gp(D) of a digraph D, defined as the maximum size of a vertex subset containing no three vertices on any common shortest directed path.

Load-bearing premise

The natural directed analogue of the undirected general position definition, requiring no three vertices on a common shortest directed path, is the correct extension to digraphs.

What would settle it

A polynomial-time algorithm that computes the general position number for every oriented graph would disprove the NP-completeness result.

Figures

Figures reproduced from arXiv: 2604.15909 by Elias John Thomas, Gabriele Di Stefano, Grahame Erskine, Haritha S, James Tuite, Ullas Chandran S.V..

Figure 1
Figure 1. Figure 1: A gp-set in a digraph (vertices in red) u, v ∈ S, no shortest u, v-path in D passes through a vertex in S − {u, v}. The number of vertices in a largest general position set of D is the general position number gp(D) of D, and such a largest set is a gp-set of D. The recent paper [29] of Stojanovi´c investigates the related mutual visibility problem in directed graphs. A subset S ⊆ V (G) of a connected undir… view at source ↗
Figure 2
Figure 2. Figure 2: The digraph K(5, 5) (with a largest mutual visibility set in blue) Theorem 2.3. For any b ≥ a ≥ 2 there exists a strong digraph D with gp(D) = a and µ(D) = b. Proof. As noted above, we have gp(D) ≤ µ(D) for any digraph. If a = b, then the complete digraph Ka suffices. When b > a we use the following construction. Let K(r) be the digraph with vertex set {ui , vi : i ∈ Zr+1} with all four arcs from {ui , vi}… view at source ↗
Figure 3
Figure 3. Figure 3: Two examples of Φ(D) from the proof of Theorem 2.18 with optimal general position sets in red, applied to an oriented path (above) and an oriented cycle (below). Corollary 2.17. For any oriented graph D, gp(D) ≤ −→a (D). The paper [5] defines the gp-chromatic number χgp(G) of a graph G to be the smallest number of colours needed to colour the vertices of G such that each colour class is in general position… view at source ↗
Figure 4
Figure 4. Figure 4: The Kautz digraph Ka(5, 2) and a maximal gp-set 13 [PITH_FULL_IMAGE:figures/full_fig_p013_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: A tree and its converse with gp number 5 [PITH_FULL_IMAGE:figures/full_fig_p016_5.png] view at source ↗
read the original abstract

The general position number for graphs ask for largest vertex subsets $S$ such that no three vertices are contained on a common shortest path. We examine this problem in the setting of directed graphs. We provide bounds for the general position number of digraphs, show that the problem is NP-complete for oriented graphs, investigate the problem for some important families of digraphs such as circulant digraphs, Kautz digraphs and permutation digraphs, and study the general position numbers obtained from all orientations of an undirected graph.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The paper extends the general position number gp(G) from undirected graphs—largest S with no three vertices on a common shortest path—to digraphs, using the natural analogue that no three vertices lie on a common shortest directed path. It derives general bounds, proves NP-completeness of computing gp(D) for oriented graphs, obtains exact values or tight bounds for circulant digraphs, Kautz digraphs and permutation digraphs, and determines the possible gp values over all orientations of a fixed undirected graph.

Significance. The NP-completeness result for oriented graphs is a solid contribution, as is the systematic treatment of standard families that supplies concrete benchmarks. The orientation study connects the directed and undirected settings. If the proofs hold, the work supplies a coherent starting point for directed general-position problems with potential follow-up in network theory and extremal digraph combinatorics.

major comments (2)
  1. [§3] §3 (NP-completeness): the reduction from the undirected general-position problem to oriented graphs must explicitly verify that the added orientations do not create new shortest directed paths that would invalidate the equivalence; the current sketch leaves open whether the constructed digraph preserves the original shortest-path triples exactly.
  2. [§4.3] §4.3 (permutation digraphs): the claimed formula gp(D) = n − c(D) where c(D) counts cycles appears to rest on an unstated assumption that every shortest path is contained in a single cycle; a counter-example on a 4-cycle with a chord would falsify the bound and should be ruled out or the statement corrected.
minor comments (3)
  1. [Definition 2.1] Definition 2.1: the phrase “common shortest directed path” should be expanded to “directed path that is shortest between its endpoints” to preclude ambiguity with non-shortest paths.
  2. [Table 2] Table 2: several rows list only lower bounds without citing the matching upper-bound theorem or construction; add cross-references.
  3. [Introduction] The abstract claims “bounds for the general position number of digraphs” but the introduction does not state whether these are absolute or in terms of other digraph parameters; clarify the scope.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation and the specific comments, which help strengthen the presentation. We respond point by point to the major remarks below.

read point-by-point responses

  1. Referee: [§3] §3 (NP-completeness): the reduction from the undirected general-position problem to oriented graphs must explicitly verify that the added orientations do not create new shortest directed paths that would invalidate the equivalence; the current sketch leaves open whether the constructed digraph preserves the original shortest-path triples exactly.

    Authors: We agree that the sketch in Section 3 would be improved by an explicit verification step. In the reduction the orientations are selected so that every shortest directed path in the constructed oriented graph is a shortest path of the original undirected graph and no shorter directed paths are introduced. We will revise the proof to include a short lemma confirming that the set of shortest-path triples is preserved exactly, thereby completing the equivalence. revision: yes

  2. Referee: [§4.3] §4.3 (permutation digraphs): the claimed formula gp(D) = n − c(D) where c(D) counts cycles appears to rest on an unstated assumption that every shortest path is contained in a single cycle; a counter-example on a 4-cycle with a chord would falsify the bound and should be ruled out or the statement corrected.

    Authors: Permutation digraphs are defined as the functional digraphs of permutations and therefore consist exclusively of vertex-disjoint directed cycles (in-degree and out-degree exactly one at every vertex). A 4-cycle with a chord necessarily has a vertex of out-degree two and is excluded by the definition. Consequently every shortest path lies inside a single cycle and the formula holds. We will insert one clarifying sentence in §4.3 stating the degree condition and noting that chorded examples lie outside the class under consideration. revision: partial

Circularity Check

0 steps flagged

No circularity detected; results are independent combinatorial proofs

full rationale

The paper defines the directed general position number via a direct, non-circular extension of the undirected concept (no three vertices on a shortest directed path). It then proves bounds, NP-completeness via explicit reductions for oriented graphs, and exact values for specific families (circulants, Kautz, permutations) using standard graph-theoretic arguments. No equations reduce a claimed prediction to a fitted parameter by construction, no load-bearing self-citations close the central claims, and no ansatz or renaming is smuggled in. The derivation chain consists of independent proofs and reductions that stand on their own without referencing the target results as inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no explicit axioms, free parameters, or invented entities are stated. The central claim rests on the unstated assumption that the undirected definition extends directly to digraphs.

pith-pipeline@v0.9.0 · 5393 in / 1029 out tokens · 18348 ms · 2026-05-10T08:29:13.839051+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages

  1. [1]

    N. Alon, D. Mubayi, R. Thomas, Large induced forests in sparse graphs, J. Graph Theory 38 (3) (2001) 113–123

    work page 2001

  2. [2]

    B. S. Anand, U. Chandran S.V., M. Changat, S. Klavˇ zar, E. J. Thomas, Characteri- zation of general position sets and its applications to cographs and bipartite graphs, Appl. Math. Comput. 359 (2019) 84–89

    work page 2019

  3. [3]

    P. N. Balister, E. Gy˝ ori, J. Lehel, R. H. Schelp, Connected graphs without long paths, Discrete Math. 308 (19) (2008) 4487–4494

    work page 2008

  4. [4]

    J. M. Brunat, M. A. Fiol, M. L. Fiol, Digraphs on permutations, Discrete Math. 174 (1-3) (1997) 73–86

    work page 1997

  5. [5]

    Chandran S.V., G

    U. Chandran S.V., G. Di Stefano, H. Sreelatha, E.J. Thomas, J. Tuite, Colouring a graph with position sets, Ars. Math. Contemp. (2025), in pressdoi.org/10.26493/ 1855-3974.3454.a3c

    work page arXiv 2025

  6. [6]

    Ullas Chandran S, S

    U. Chandran S.V., S. Klavˇ zar, J. Tuite, The general position problem: a survey (2026)https://doi.org/10.48550/arXiv.2501.19385

    work page doi:10.48550/arxiv.2501.19385 2026

  7. [7]

    Chandran S

    U. Chandran S. V., G. J. Parthasarathy, The geodesic irredundant sets in graphs, Int. J. Math. Combin. 4 (2016) 135–143

    work page 2016

  8. [8]

    G. J. Chang, L. D. Tong, H. T. Wang, Geodetic spectra of graphs, Eur. J. Combin. 25 (2004) 383–391

    work page 2004

  9. [9]

    Chartrand, P

    G. Chartrand, P. Zhang, The geodetic number of an oriented graph, Eur. J. Combin. 21 (2000) 181—189

    work page 2000

  10. [10]

    Cornaz, A

    D. Cornaz, A. R. Mahjoub, The maximum induced bipartite subgraph problem with edge weights, SIAM J. Discrete Math. 21 (3) (2007) 662–675

    work page 2007

  11. [11]

    Dirac, Extensions of Tur´ an’s theorem on graphs, Acta Hung

    G. Dirac, Extensions of Tur´ an’s theorem on graphs, Acta Hung. Acad. Sci. 14 (1963) 417–422

    work page 1963

  12. [12]

    Di Stefano, Mutual visibility in graphs, Appl

    G. Di Stefano, Mutual visibility in graphs, Appl. Math. Comput. 419 (2022) 126850

    work page 2022

  13. [13]

    Di Stefano, S

    G. Di Stefano, S. Klavˇ zar, A. Krishnakumar, J. Tuite, I. G. Yero, Lower general position sets in graphs, Discuss. Math. Graph Theory 45 (2) (2025) 509–531

    work page 2025

  14. [14]

    L. Dong, C. Lu, X. Wang, The upper and lower geodetic numbers of graphs, Ars Comb. 91 (2005)

    work page 2005

  15. [15]

    H. E. Dudeney, Amusements in Mathematics, Nelson, Edinburgh, 1917

    work page 1917

  16. [16]

    Erd˝ os, Extremal problems in graph theory, Theory of graphs and its applications, Proc

    P. Erd˝ os, Extremal problems in graph theory, Theory of graphs and its applications, Proc. Sympos. Smolenice, Publ. House Czech. Acad. Sci., Prague (1964) 29–36

    work page 1964

  17. [17]

    Ertem, E

    Z. Ertem, E. Lykhovyd, Y. Wang, S. Butenko, The maximum independent union of cliques problem: complexity and exact approaches, J. Glob. Optim. 76 (3) (2020) 545–562. 26

    work page 2020

  18. [18]

    I. B. Hartman, Variations on the Gallai-Milgram Theorem, Discrete Math. 71 (2) (1988) 95–105

    work page 1988

  19. [19]

    R. M. Karp, Reducibility among combinatorial problems. In: Complexity of Com- puter Computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y. 1972) 85–103

    work page 1972

  20. [20]

    Klavˇ zar, D

    S. Klavˇ zar, D. Kuziak, I. Peterin, I. G. Yero, A Steiner general position problem in graph theory, Comput. Appl. Math. 40 (6) (2021) 1–15

    work page 2021

  21. [21]

    Klavˇ zar, D

    S. Klavˇ zar, D. F. Rall, I. G. Yero, Generald-position sets, Ars Math. Contemp. 21 (1) (2021) 1-03

    work page 2021

  22. [22]

    Klavˇ zar, I

    S. Klavˇ zar, I. G. Yero, The general position problem and strong resolving graphs, Open Math. 17 (1) (2019) 1126–1135

    work page 2019

  23. [23]

    Lu, The geodetic numbers of graphs and digraphs, Sci

    C. Lu, The geodetic numbers of graphs and digraphs, Sci. China. Ser. A 50 (2007) 1163—1172

    work page 2007

  24. [24]

    Magnant, D

    C. Magnant, D. M. Martin, A note on the path cover number of regular graphs, Australas. J. Comb. 43 (2009) 211–218

    work page 2009

  25. [25]

    Manuel, S

    P. Manuel, S. Klavˇ zar, A general position problem in graph theory, Bull. Aust. Math. Soc. 98 (2018) 177–187

    work page 2018

  26. [26]

    Manuel, R

    P. Manuel, R. Prabha, S. Klavˇ zar, The edge general position problem, Bull. Malay. Math. Sci. Soc. 45 (6) (2022) 2997–3009

    work page 2022

  27. [27]

    R. M. McConnell, J. P. Spinrad, Linear-time transitive orientation, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, (1997) 19–25

    work page 1997

  28. [28]

    Reed, Paths, stars and the number three, Combin

    B. Reed, Paths, stars and the number three, Combin. Probab. Comput. 5 (3) (1996) 277–295

    work page 1996

  29. [29]

    Stojanovi´ c, The mutual-visibility problem in directed graphs (2026)https:// doi.org/10.48550/arXiv.2602.03267

    V. Stojanovi´ c, The mutual-visibility problem in directed graphs (2026)https:// doi.org/10.48550/arXiv.2602.03267

    work page doi:10.48550/arxiv.2602.03267 2026

  30. [30]

    E. J. Thomas, U. Chandran S. V., J. Tuite, G. Di Stefano, On monophonic position sets in graphs, Discrete Appl. Math. 354 (2024) 72–82. 27

    work page 2024