Note on a Turán-type Problem on Distances

Abstract

A new Turán-type problem on distances of graphs was introduced by Tyomkyn and Uzzell. In this paper, we focus on the case of distance two. We show that for any positive integer $n$, a graph $G$ on $n$ vertices without three vertices pairwise at distance $2$ has at most $\frac{(n-1{)}^2}{4}+1$ pairs of vertices at distance $2$, provided $G$ has a vertex $v\in V(G)$ whose neighbors are covered by at most two cliques. This partially answers a conjecture of Tyomkyn and Uzzell [Tyomkyn, M.,Uzzell, A.J.: A new Turdn-type problem on distances of graphs. Graphs Combin. $29(6),1927-1942(2012)$]..