An Upper Bound on the Number of Edges of a Graph Whose kth Power Has a Connected Complement

Abstract

We say that a graph is k-wide if for any partition of its vertex set into two subsets, one can choose vertices at distance at least k in these subsets (i.e., the complement of the kth power of this graph is connected). We say that a graph is k-mono-wide if for any partition of its vertex set into two subsets, one can choose vertices at distance exactly k in these subsets.

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 ≥ 4: the complement of a k-wide graph contains at least (n − 2k)(2k − 4[log₂k] − 1) edges.