An upper bound on the number of edges of a graph which $k$-th power has connected complement

We call a graph $k$-wide, if for any division of its vertex set into two sets one can choose vertices of distance at least $k$ in these sets (i.e., the complement of $k$-th power of this graph is connected). We call a graph $k$-mono-wide, if for any division of its vertex set into two sets one can choose vertices of distance exactly $k$ in these sets.
We prove that the complement of a $3$-wide graph on $n$ vertices has at least $3n-7$ edges and the complement of a $3$-mono-wide graph on $n$ vertices has at least $3n-8$ edges. We construct infinite series of graphs for which these bounds are attained.
We also prove an asymptotically tight bound for the case $k\ge4$: the complement of a $k$-wide graph contains at least $(n-2k)(2k-4[\log_2k]-1)$ edges.