{"id":"arxiv/2604.20787","url":"https://arxiv.org/abs/2604.20787","tags":["math.CO"],"score":0,"title":"Computing the Exchange Number in Graphs with respect to Cycle Convexity","domain":"math.CO","source":"arxiv","authors":["Revathy S. Nair","Bijo S. Anand","Julliano R. Nascimento"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-22","reactions":{}}