Criteria on forbidden subgraphs in the complements for positive Lin--Lu--Yau curvature

Abstract

We investigate forbidden subgraph conditions in the complement of a graph that guarantee positive Lin--Lu--Yau curvature. In particular, we prove that every graph whose complement contains no $4$-cycles has positive Lin--Lu--Yau curvature, with the only exception of the $4$-vertex path. We further prove that, for any integer $t\ge 2$, every graph on at least $\max \{t^2-2t+2,8t\}$ vertices whose complement contains no $K_{2,t}$ has positive curvature. In addition, this lower bound on the number of vertices is optimal for $t\ge 10$. Finally, we construct examples showing that, in general, the forbidden subgraphs in these results cannot be replaced by cycles of length other than $4$ or by complete bipartite graphs $K_{s,t}$ with $s>2$ and $t>2$.

15 pages, 1 figure. All comments are welcome!