A Turán-Type Problem on Distances in Graphs
A Turán-Type Problem on Distances in Graphs
复制标题
DOI：
10.1007/s00373-012-1225-4
复制
发表时间：
2010-11
影响因子：
0.7
通讯作者：
Mykhaylo Tyomkyn;Andrew J. Uzzell
中科院分区：
文献类型：
--
作者：
Mykhaylo Tyomkyn;Andrew J. Uzzell
我们提出了一类关于图中距离的新问题，并做了几个猜想。作为证明它们的第一步，我们证明了对于足够大的nandk值，一个在距离上没有三个顶点成对的图在距离上最多有（n−k+ 1）2/4对顶点。
We suggest a new type of problem about distances in graphs and make several conjectures. As a first step towards proving them, we show that for sufficiently large values ofnandk, a graph onnvertices that has no three vertices pairwise at distancekhas at most (n−k+ 1)2/4 pairs of vertices at distancek.