Positively Lin-Lu-Yau curved graphs with no $K_{2,t}$ minor

Abstract

Let $G$ be a connected graph with minimum degree at least two, positive Lin-Lu-Yau Ricci curvature, and no $K_{2,t}$ minor, where $t\ge 3$ is an integer. We first establish tight upper bounds on the maximum degree of $G$ by showing that $\Delta (G)\le 2t+3$ for $t=4$, $\Delta (G)\le 2t+4$ for $t\in \{5,6\}$, and $\Delta (G)\le 2t+2$ for all $t\ge 7$. We then prove that $G$ has at most $10$ vertices for $t=3$, and at most $(t+1)\left(\Delta (G{)}^2(\Delta (G)-1)/2+1\right)$ vertices for all $t\ge 4$.

arXiv comment17 pages