Formulas and Upper Bounds for the Carath{é}odory Number of Hamming Graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915474475843584 |
|---|---|
| author | Dratman, Ezequiel González, Lucía M. Grippo, Luciano N. |
| author_facet | Dratman, Ezequiel González, Lucía M. Grippo, Luciano N. |
| contents | Let $G$ be a simple graph and let $S$ be a subset of its vertices. We say that $S$ is $P_3$-convex if every vertex $v \in V(G)$ that has at least two neighbors in $S$ also belongs to $S$. The $P_3$-hull set of $S$ is the smallest $P_3$-convex set of $G$ that contains $S$. Carathéodory number of a graph $G$, denoted by $c(G)$, is the smallest integer $c$ such that for every subset $S \subseteq V(G)$ and every vertex $p$ in the $P_3$-hull of $S$, there exists a subset $F \subseteq S$ with $|F| \leq c$ such that $p$ belongs to the $P_3$-hull of $F$. In this article, we present upper bounds and formulas for the $P_3$-Carathéodory number in Hamming graphs, which are defined as the Cartesian product of $n$ complete graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_01645 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Formulas and Upper Bounds for the Carath{é}odory Number of Hamming Graphs Dratman, Ezequiel González, Lucía M. Grippo, Luciano N. Combinatorics 05C69 Let $G$ be a simple graph and let $S$ be a subset of its vertices. We say that $S$ is $P_3$-convex if every vertex $v \in V(G)$ that has at least two neighbors in $S$ also belongs to $S$. The $P_3$-hull set of $S$ is the smallest $P_3$-convex set of $G$ that contains $S$. Carathéodory number of a graph $G$, denoted by $c(G)$, is the smallest integer $c$ such that for every subset $S \subseteq V(G)$ and every vertex $p$ in the $P_3$-hull of $S$, there exists a subset $F \subseteq S$ with $|F| \leq c$ such that $p$ belongs to the $P_3$-hull of $F$. In this article, we present upper bounds and formulas for the $P_3$-Carathéodory number in Hamming graphs, which are defined as the Cartesian product of $n$ complete graphs. |
| title | Formulas and Upper Bounds for the Carath{é}odory Number of Hamming Graphs |
| topic | Combinatorics 05C69 |
| url | https://arxiv.org/abs/2509.01645 |