pith. sign in

arxiv: 2604.20787 · v1 · submitted 2026-04-22 · 🧮 math.CO

Computing the Exchange Number in Graphs with respect to Cycle Convexity

Revathy S. Nair , Bijo S. Anand , Julliano R. Nascimento This is my paper

Pith reviewed 2026-05-09 23:47 UTC · model grok-4.3

classification 🧮 math.CO
keywords cycle convexityexchange numberNP-completenessK5-free graphschordal graphsgraph productsCartesian product
0
0 comments X

The pith

Deciding whether the exchange number of a graph under cycle convexity meets or exceeds k is NP-complete even for K5-free graphs.

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

The paper examines how hard it is to compute the exchange number of a graph when convexity is defined by cycles. A set is cycle-convex if adding any missing vertex never produces a cycle that passes through the new vertex in the induced subgraph. This matters to a reader because it separates graph classes where the number can be found quickly from those where it is intractable in general. The work proves the decision version is NP-complete on K5-free graphs, characterizes graphs achieving the absolute maximum value of n-1, and supplies closed formulas plus polynomial algorithms for chordal graphs whose blocks form a single chain. It also derives lower bounds for Cartesian products and exact expressions for strong and lexicographic products.

Core claim

Given a graph G and positive integer k, deciding whether e_cc(G) ≥ k is NP-complete even if G is K5-free. All n-vertex graphs with exchange number exactly n-1 are characterized. Closed formulas exist for the exchange number of chordal graphs whose blocks lie in a single chain, yielding polynomial-time algorithms. A lower bound holds for the Cartesian product of arbitrary graphs, and explicit formulas are obtained for the exchange number of strong and lexicographic products.

What carries the argument

Cycle-convex sets, where S is cycle-convex if G[S ∪ {v}] contains no cycle through any added vertex v, together with the exchange number e_cc(G) defined as the largest cardinality of an E-independent set in this convexity.

If this is right

  • The exchange number cannot be computed in polynomial time for K5-free graphs unless P equals NP.
  • Graphs attaining exchange number n-1 are fully described by the given characterization.
  • Chordal graphs with blocks forming a single chain admit a closed formula and therefore polynomial-time evaluation.
  • Lower bounds and explicit formulas are available for the exchange numbers of Cartesian, strong, and lexicographic products.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The persistence of hardness on K5-free graphs suggests cycle convexity may remain difficult under other forbidden-subgraph restrictions.
  • Tractability when blocks are chained points to block-cutvertex structure as the feature that controls computability of the exchange number.
  • The product formulas indicate that the exchange number respects certain graph operations, allowing its value on large graphs to be assembled from smaller components.

Load-bearing premise

The reduction establishing NP-completeness maps known hard instances to K5-free graphs while correctly preserving the value of the exchange number.

What would settle it

A polynomial-time algorithm that correctly computes e_cc(G) for every K5-free graph would refute the NP-completeness claim.

Figures

Figures reproduced from arXiv: 2604.20787 by Bijo S. Anand, Julliano R. Nascimento, Revathy S. Nair.

Figure 1
Figure 1. Figure 1: Sketch of the graph G constructed for Theorem 5 from an instance of 3-SAT, where x ∈ C1 and x ∈ C2. The double edges represent all the possible edges between vertices in the two rectangles. The construction produces a graph G with 12 vertices for every clause gadget Gci , plus 3 vertices from D ∪Z, plus 4 vertices for every pair of opposite literals. Then |V (G)| ≤ 12m+ 3 + 4 ·O(m2 ) = O(m2 ) and the const… view at source ↗
Figure 2
Figure 2. Figure 2: A chain of blocks in which uv /∈ E(G), ui ∈ V (Bi), u′ i ∈ V (B′ i ) for 1 ≤ i ≤ k, NG(V (B)) ∩ S = ∅ and Γ ′ B(u, v) = Hullcc(u, v) = {u, v} [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: A chain of blocks in which uv ∈ E(G), ui ∈ V (Bi), u′ i ∈ V (B′ i ) for 1 ≤ i ≤ k, NG(V (B)) ∩ S = ∅ and Γ ′ B(u, v) = Hullcc(u, v) = V (B). (b) Let B ∈ B(G) is not an end block of G and {u, v} ⊆ V (B) are the cut vertices of G. Con￾sider the set S = {u, v, u1, u′ 1 , u2, u′ 2 , . . . , uk, u′ k} ⊆ V (G) and NG(V (B)) ∩ S ̸= ∅. Let u1 ∈ NG(V (B))∩V (B1), u2 ∈ NG(V (B1))∩V (B2), . . . , uk ∈ NG(V (Bk−1))∩V … view at source ↗
Figure 4
Figure 4. Figure 4: A chain of blocks where uv /∈ E(G), u1 ∈ NG(v) ∩ V (B1), u2 ∈ NG(V (B1)) ∩ V (B2), . . . , uk ∈ NG(V (Bk−1))∩V (Bk), u′ 1 ∈ NG(u)∩V (B′ 1 ), u′ 2 ∈ NG(V (B′ 1 ))∩V (B′ 2 ), . . . , u′ k ∈ NG(V (B′ k−1 )) ∩ V (B′ k ) with Γ ′′ B(u, v) = [ k i=1 V (Bi) ∪ V (B ′ i ) [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: A chain of blocks where uv ∈ E(G), u1 ∈ NG(v) ∩ V (B1), u2 ∈ NG(V (B1)) ∩ V (B2), . . . , uk ∈ NG(V (Bk−1))∩V (Bk), u′ 1 ∈ NG(u)∩V (B′ 1 ), u′ 2 ∈ NG(V (B′ 1 ))∩V (B′ 2 ), . . . , u′ k ∈ NG(V (B′ k−1 )) ∩ V (B′ k ) with Γ ′′ B(u, v) = V (B) ∪ [ k i=1 V (Bi) ∪ V (B ′ i ). We use the notation ΓB(u, v) to denote Γ ′ B(u, v) S Γ ′′ B(u, v) in the proof of the Theorem 14. Before proceeding to our next results, … view at source ↗
Figure 6
Figure 6. Figure 6: An example graph where x, y ∈ V (B) satisfy the vertex-separation property. 10 [PITH_FULL_IMAGE:figures/full_fig_p010_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: , we have the following properties: Hullcc(S \ {u1}) = S \ {u1}, Hullcc(S \ {u ′ 1}) = S \ {u ′ 1}, Hullcc(S \ {u ′ k}) = V (G) and [ l i̸=k,i=2 Hullcc(S \ {ui}) = l [−1 i=1 V (Bi) ∪ {ul}. Then, Hullcc(S \ {u ′ k}) ̸⊆ [ a∈S\{u ′ k } Hullcc(S \ {a}) and thus, S is an E-independent set containing l + 2 vertices [PITH_FULL_IMAGE:figures/full_fig_p012_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: A chordal graph G containing blocks B1, B2, . . . , Bl and vertices u1, u′ 1 , u′′ 1 , u2, . . . , ul such that {u1, u′ 1 , u′′ 1} ⊆ V (B1), ui ∈ N(V (Bi−1)) ∩ V (Bi) for 2 ≤ i ≤ l with {u1, u′ 1 , u′′ 1} satisfy the edge-vertex property. Here, u ′′ 1 is the pivot of S. Now, it remains to show that there does not exists an E-independent set of size larger than l + 2. Assume that G contains an E-independent… view at source ↗
read the original abstract

Given a graph $G$, a subset $S \subseteq V(G)$ is \textit{cycle convex}, if for any vertex $v \in V(G) \setminus S$, the induced subgraph, $G[S \cup \{v\}]$ cannot form a cycle containing the vertex $v$. The \textit{exchange number} of $G$, denoted by $e_{cc}(G)$ is the maximum cardinality of an $\textit{$E$-independent}$ set of $G$. This paper studies the computational complexity of determining the exchange number of graphs and provides exact values for some graph classes. Given a graph $G$ and a positive integer $k$, we show that deciding whether $e_{cc}(G) \geq k$ is NP-complete even if $G$ is a $K_5$-free graph. In contrast, we characterize all $n$-vertex graphs $G$ with exchange number $n-1$ and obtain closed formulas for chordal graphs $G$ whose blocks lie in a single chain, which leads to polynomial-time algorithms for computing $e_{cc}(G)$. We also establish a lower bound for the exchange number of the Cartesian product of general graphs and by using the results of Anand et al. \cite{bijo2}, we derive an explicit formula for the exchange number of strong and lexicographic graph products.

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

0 major / 3 minor

Summary. The manuscript defines cycle-convex sets and the exchange number e_cc(G) as the size of a maximum E-independent set under cycle convexity. It proves that deciding whether e_cc(G) >= k is NP-complete even for K5-free graphs, characterizes all n-vertex graphs with e_cc(G) = n-1, derives closed formulas for chordal graphs whose blocks form a single chain (yielding polynomial-time algorithms), establishes a lower bound on e_cc for Cartesian products, and obtains explicit formulas for strong and lexicographic products via results of Anand et al.

Significance. The NP-completeness result for K5-free graphs is a solid contribution, showing that the problem remains hard on a natural restricted class. The characterizations and closed formulas for chordal graphs and products supply exact values and efficient computation for concrete families, which is useful for the study of convexity parameters. The lower bound and product formulas extend the reach of the work without introducing new parameters.

minor comments (3)
  1. [§3] §3 (NP-completeness reduction): the constructed instances should explicitly verify that the reduction preserves K5-freeness; a short paragraph confirming no K5 is created would strengthen the claim.
  2. [§2] The notation for E-independent sets is introduced without a displayed definition; adding a formal definition box or equation would improve readability.
  3. [§5] In the product formulas (using Anand et al.), state the precise theorem or corollary from the cited paper that is applied, rather than a general reference.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful summary of our manuscript, the positive assessment of its significance, and the recommendation for minor revision. We appreciate the recognition of the NP-completeness result on K5-free graphs and the contributions on characterizations, formulas, and product graphs.

Circularity Check

0 steps flagged

No significant circularity; minor self-citation for product formulas

full rationale

The paper's core result is an NP-completeness proof for deciding whether e_cc(G) >= k on K5-free graphs, obtained via a standard polynomial reduction from a known NP-complete problem that preserves the K5-free property. This reduction and the characterizations of graphs with e_cc(G) = n-1, plus closed formulas for certain chordal graphs, rest directly on the foundational definitions of cycle-convex sets and E-independent sets without reducing any claim to its own inputs. The sole self-citation (to Anand et al. for strong/lexicographic product formulas) supports a secondary result on products and is not load-bearing for the primary complexity or characterization claims. No step equates a derived quantity to a fitted parameter or prior self-result by construction, so the derivation remains self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The paper uses only standard mathematical definitions of graphs, induced subgraphs, cycles, and convexity; no free parameters are fitted, no new entities are postulated, and no ad-hoc axioms beyond ordinary graph theory are introduced.

pith-pipeline@v0.9.0 · 5551 in / 1250 out tokens · 69505 ms · 2026-05-09T23:47:27.149676+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

28 extracted references · 28 canonical work pages

  1. [1]

    Bijo S Anand, Arun Anil, Manoj Changat, Mitre C Dourado, and Sabeer S Ramla,Computing the hull number in∆-convexity, Theoretical Computer Science844(2020), 217–226

    work page 2020

  2. [2]

    292– 306

    Bijo S Anand, Arun Anil, Manoj Changat, Revathy S Nair, and Prasanth G Narasimha-Shenoi, Helly Number, Radon Number and Rank in∆-Convexity on Graphs, Proceedings of the Confer- ence on Algorithms and Discrete Applied Mathematics (CALDAM), Springer, 2025, pp. 292– 306

    work page 2025

  3. [3]

    Bijo S Anand, Arun Anil, Manoj Changat, Prasanth G Narasimha-Shenoi, and Sabeer S Ramla, Carathéodorynumberandexchangenumberin∆-convexity,J.Combin.Math.Combin.Comput 126(2025), no. 11, 27. 18

    work page 2025

  4. [4]

    Bijo S Anand, Prasanth G Narasimha-Shenoi, and Sabeer Sain Ramla,∆-Convexity Number and∆-NumberofGraphsandGraphProducts,ConferenceonAlgorithmsandDiscreteApplied Mathematics, Springer, 2020, pp. 209–218

    work page 2020

  5. [5]

    BijoSAnand,UllasChandranSV,ManojChangat,MitreCDourado,FerdoosHosseinNezhad, and Prasanth G Narasimha-Shenoi,On the carathéodory and exchange numbers of geodetic convexity in graphs, Theoretical Computer Science804(2020), 46–57

    work page 2020

  6. [6]

    Bijo S Anand, Ullas Chandran SV, Julliano R Nascimento, and Revathy S Nair,Complexity and structural results for the hull and convexity numbers in cycle convexity for graph products, Discrete Applied Mathematics377(2025), 552–561

    work page 2025

  7. [7]

    Júlio Araújo, Victor Campos, Darlan Girão, João Nogueira, António Salgueiro, and Ana Silva, Cycle convexity and the tunnel number of links, arXiv preprint arXiv:2012.05656 (2020), 1–28

    work page arXiv 2012

  8. [8]

    Julio Araujo, Victor Campos, Darlan Girão, João Nogueira, António Salgueiro, and Ana Silva, On the hull number on cycle convexity of graphs, Information Processing Letters183(2024), 106420

    work page 2024

  9. [9]

    Júlio Araújo, Victor Campos, Darlan Girão, João Nogueira, António Salgueiro, and Ana Silva, On the hull number on cycle convexity of graphs, Information Processing Letters183(2024), 106420

    work page 2024

  10. [10]

    Júlio Araújo, Mitre C Dourado, Fábio Protti, and Rudini M Sampaio,Introduction to graph convexity: An algorithmic approach, Springer Nature, 2025

    work page 2025

  11. [11]

    JulioAraujo,GuillaumeDucoffe,NicolasNisse,andKarolSuchan,Onintervalnumberincycle convexity,DiscreteMathematics&TheoreticalComputerScience20(2018),no.GraphTheory

    work page 2018

  12. [12]

    3, 929–939

    Rommel M Barbosa, Erika MM Coelho, Mitre C Dourado, Dieter Rautenbach, and Jayme L Szwarcfiter,Onthecarathéodorynumberfortheconvexityofpathsoforderthree,SIAMJournal on Discrete Mathematics26(2012), no. 3, 929–939

    work page 2012

  13. [13]

    JCáceres, CHernando, MMora, MPuertas, andCSeara,Onmonophonic setsingraphs, 2005

    work page 2005

  14. [14]

    3, 726–736

    JoséCáceres,AlbertoMárquez,andMaríaLuzPuertas,Steinerdistanceandconvexityingraphs, European Journal of Combinatorics29(2008), no. 3, 726–736

    work page 2008

  15. [15]

    Victor Campos, Rudini M Sampaio, Ana Silva, and Jayme L Szwarcfiter,Graphs with fewP4’s under the convexity of paths of order three, Discrete Applied Mathematics192(2015), 28–39

    work page 2015

  16. [16]

    Carmen C Centeno, Mitre C Dourado, Lucia Draque Penso, Dieter Rautenbach, and Jayme L Szwarcfiter,Irreversibleconversionofgraphs,TheoreticalComputerScience412(2011),no.29, 3693–3700

    work page 2011

  17. [17]

    Erika M. M. Coelho, Hebert Coelho, Julliano R. Nascimento, and Jayme L. Szwarcfiter,On the P3-hull number of some products of graphs, Discrete Applied Mathematics253(2019), 2–13

    work page 2019

  18. [18]

    12, 1268–1274

    Mitre C Dourado, Fábio Protti, and Jayme L Szwarcfiter,Complexity results related to mono- phonic convexity, Discrete Applied Mathematics158(2010), no. 12, 1268–1274

    work page 2010

  19. [19]

    7, 1615–1627

    Paul A Dreyer Jr and Fred S Roberts,Irreversiblek-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion, Discrete Applied Mathematics157 (2009), no. 7, 1615–1627. 19

    work page 2009

  20. [20]

    Minimal path convexity, Journal of Combinatorial Theory, Series B44(1988), no

    Pierre Duchet,Convex sets in graphs, II. Minimal path convexity, Journal of Combinatorial Theory, Series B44(1988), no. 3, 307–316

    work page 1988

  21. [21]

    3, 217–223

    Martin G Everett and Stephen B Seidman,The hull number of a graph, Discrete Mathematics 57(1985), no. 3, 217–223

    work page 1985

  22. [22]

    F Harary F Buckley,Distances in graphs, Eddison Wesley, Redwood City CA, 1990

    work page 1990

  23. [23]

    3, 433–444

    Martin Farber and Robert E Jamison,Convexity in graphs and hypergraphs, SIAM Journal on Algebraic Discrete Methods7(1986), no. 3, 433–444

    work page 1986

  24. [24]

    174, Freeman San Francisco, 1979

    Michael R Garey and David S Johnson,Computers and intractability, vol. 174, Freeman San Francisco, 1979

    work page 1979

  25. [25]

    MartinCharlesGolumbic,Algorithmicgraphtheoryandperfectgraphs,vol.57,Elsevier,2004

    work page 2004

  26. [26]

    Carlos V G C Lima, Thiago Marcilon, and Pedro P Medeiros,The complexity of convexity number and percolation time in the cycle convexity, arXiv preprint arXiv:2404.09236 (2024), 1–24

    work page arXiv 2024

  27. [27]

    577, Springer, 2013

    Ignacio M Pelayo,Geodesic convexity in graphs, vol. 577, Springer, 2013

    work page 2013

  28. [28]

    van De Vel,Theory of convex structures, Elsevier, 1993

    Marcel L.J. van De Vel,Theory of convex structures, Elsevier, 1993. 20

    work page 1993