Formulas and Upper Bounds for the Carath{é}odory Number of Hamming Graphs

Abstract

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|\le 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.