Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 30 min ago
PreprintCC BY 4.0arXiv

Computing the Helly Number, Radon Number and Rank in Cycle Convexity

  • Revathy S. Nair
  • Bijo S. Anand
  • Ullas Chandran S. V.
  • Julliano R. Nascimento
  • Arun Anil
Open at sourcePDFDOICite

Abstract

In this paper, we investigate three fundamental convexity parameters of graphs under cycle convexity, namely the Helly number, Radon number, and rank. We first study the computational complexity of these parameters. For each of these parameters, we consider the associated threshold decision problem of determining whether the parameter of a given graph is at least a prescribed integer. We establish that all three problems are NP-hard and W[1]-hard when parameterized by the threshold. Moreover, we strengthen these results by showing that the NP-hardness persists even when the input is restricted to planar graphs of maximum degree at most $6$. We also focus on the structural properties of connected graphs corresponding to extremal values of these parameters. In particular, we characterize the graph classes for which the three parameters attain the values n−1 and n−2, where n is the order of G.

Related

  1. A Radon-Nikodým theorem for Fuzzy Number Multimeasures in Locally Convex Spaces
    Sokol Kaliaj
    arXivPreprintCC BY 4.0Full textStatisticsarXiv
  2. The Multicolour Size--Ramsey Number of an Even Cycle
    Lanchao Wang, Xiaolin Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. On the Turán number for the Cartesian product of an odd cycle and a tree
    Ya-Hong Chen, Yong Lu, Quan Sun +2
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. An improved lower bound for the packing number of the 2-token graph of the cycle
    Luis Manuel Rivera
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Computing and Bounding the Number of Eulerian Orientations for Certain Classes of $4$-Regular Graphs
    Evangelos Bartzos, Michalis Samaris
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{nair2026computing,
  title = {{Computing the Helly Number, Radon Number and Rank in Cycle Convexity}},
  author = {Revathy S. Nair and Bijo S. Anand and Ullas Chandran S. V. and Julliano R. Nascimento and Arun Anil},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.34236},
  eprint = {2609.34236},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.34236},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Computing the Helly Number, Radon Number and Rank in Cycle Convexity
AU  - Revathy S. Nair
AU  - Bijo S. Anand
AU  - Ullas Chandran S. V.
AU  - Julliano R. Nascimento
AU  - Arun Anil
PY  - 2026
DA  - 2026/09/28
PB  - arXiv
DO  - 10.48550/arxiv.2609.34236
UR  - https://arxiv.org/abs/2609.34236
AB  - In this paper, we investigate three fundamental convexity parameters of graphs under cycle convexity, namely the Helly number, Radon number, and rank. We first study the computational complexity of these parameters. For each of these parameters, we consider the associated threshold decision problem of determining whether the parameter of a given graph is at least a prescribed integer. We establish that all three problems are NP-hard and W[1]-hard when parameterized by the threshold. Moreover, we strengthen these results by showing that the NP-hardness persists even when the input is restricted to planar graphs of maximum degree at most $6$. We also focus on the structural properties of connected graphs corresponding to extremal values of these parameters. In particular, we characterize the graph classes for which the three parameters attain the values n−1 and n−2, where n is the order of G.
ER  -