Metraipolis › archive › dc_cddaf6dd07d9
Tight bounds on the Carathéodory and exchange numbers in $\triangle$-convexity — arXiv:2609.34441
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.34441
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T23:29:12.964Z
- SHA-256 of the archived text
2e4c4d1a86d126568c3c17d199643d32aa8d2d6f54647fa59690b03860b26c89- Stable URL of this page
https://metraipolis.com/documento/dc_cddaf6dd07d9
How to cite
Tight bounds on the Carathéodory and exchange numbers in $\triangle$-convexity — arXiv:2609.34441 — arXiv (en), https://arxiv.org/abs/2609.34441 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cddaf6dd07d9 (Metraipolis archive dc_cddaf6dd07d9, sha256 2e4c4d1a86d126568c3c17d199643d32aa8d2d6f54647fa59690b03860b26c89)
BibTeX
@misc{dccddaf6dd07d9,
title = {Tight bounds on the Carathéodory and exchange numbers in $triangle$-convexity — arXiv:2609.34441},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.34441},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cddaf6dd07d9; sha256 2e4c4d1a86d126568c3c17d199643d32aa8d2d6f54647fa59690b03860b26c89},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.34441. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The $\triangle$-convexity space on a finite, simple graph $G = (V,E)$ is the collection $\mathcal{C}$ of subsets $S \subseteq V(G)$ such that whenever $x \in V(G)$ forms a triangle with two vertices in $S$, we have $x \in S$. The members of $\mathcal{C}$ are called convex sets, and the convex hull of a set $S \subseteq V(G)$, denoted $\operatorname{Hull}(S)$, is the smallest member of $\mathcal{C}$ that contains $S$. The Carathéodory (resp., exchange) number, $c_{\triangle}(G)$ (resp., $e_{\triangle}(G)$), is the size of a largest Carathéodory (resp., exchange) independent subset of $V(G)$. It was shown by Anand et al. (JCMCC 126, 2025, 11--27) that $c_{\triangle}(G) \leq t(G)+1$ and $e_{\triangle}(G) \leq t(G) + 2$, where $t(G)$ is the number of triangles in $G$, and that these bounds are tight. They also computed $c_{\triangle}(G)$ and $e_{\triangle}(G)$ for a block graph $G$ in terms of the number and arrangement of non-$K_2$ blocks in $G$. In this paper, we point out a gap in the proof in Anand et al. of the first inequality, $c_{\triangle}(G) \leq t(G)+1$, which has consequences for the proof of the second inequality, $e_{\triangle}(G) \leq t(G) + 2$, as well. Moreover, the tightness results are inadvertently applied as characterizations of the extremal graphs, leading to incorrect computations of the Carathéodory and exchange numbers of block graphs in certain cases. We fix these gaps by giving a full proof of the first inequality via a different route from that in Anand et al. Together with the argument in Anand et al., this also completes the proof of the second inequality. Our proof also leads to a characterization of the extremal graphs for each bound, which we use to compute the Carathéodory and exchange numbers of block graphs and to identify the extremal block graphs. We also determine $e_{\triangle}(G)$ exactly for $k$-trees for every $k \geq 2$.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-29 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.34441 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T23:08:10.845Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).