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 k th 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 3 n − 7 edges, and the complement of a 3-mono-wide graph on n vertices has at least 3 n − 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 − 2 k )(2 k − 4[log~(2) k ] − 1) edges.
展开▼
机译：我们说如果一个图的顶点集分为两个子集，则该图是k宽的，一个人可以在这些子集中选择距离至少为k的顶点（即连接了该图的k次幂的补数）。我们说，如果对于图的顶点集的任何划分成两个子集的图，一个图可以是k个单宽的，则可以在这些子集中选择距离恰好为k的顶点。我们证明在n个顶点上的3宽图的补码至少具有3 n-7个边，而在n个顶点上的3宽图的补码至少具有3 n-8个边。我们构造图的无限系列，并获得了这些范围。我们还证明了k≥≥4的情况的渐近紧界：k宽图的补码至少包含（n −2 k）（2 k −4 [log〜（2）k] −1）边。
展开▼
