A Turan-Type Problem on Distances in Graphs

被引：3
|
作者：
Tyomkyn, Mykhaylo [1 ]
Uzzell, Andrew J. [2 ]
机构：
[1] Univ Cambridge, Dept Pure Math & Math Stat, Ctr Math Sci, Cambridge CB3 0WB, England
[2] Univ Memphis, Dept Math Sci, Memphis, TN 38152 USA
来源：
GRAPHS AND COMBINATORICS | 2013年 / 29卷 / 06期
关键词：
Distance; Turan-type problem; Forbidden subgraph; NUMBER; EDGES; SUBGRAPHS; PATHS;
D O I：
10.1007/s00373-012-1225-4
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
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 of n and k, a graph on n vertices that has no three vertices pairwise at distance k has at most (n - k + 1)(2)/4 pairs of vertices at distance k.
引用
收藏
页码：1927 / 1942
页数：16
相关论文
共 50 条
  • [1] Note on a Turan-type problem on distances
    Li, Xueliang
    Ma, Jing
    Shi, Yongtang
    Yue, Jun
    ARS COMBINATORIA, 2015, 119 : 211 - 219
  • [2] Turan-type problems for long cycles in random and pseudo-random graphs
    Krivelevich, Michael
    Kronenberg, Gal
    Mond, Adva
    JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES, 2023, 107 (04): : 1519 - 1551
  • [3] A Turán-Type Problem on Distances in Graphs
    Mykhaylo Tyomkyn
    Andrew J. Uzzell
    Graphs and Combinatorics, 2013, 29 : 1927 - 1942
  • [4] A generalized Turan problem in random graphs
    Samotij, Wojciech
    Shikhelman, Clara
    RANDOM STRUCTURES & ALGORITHMS, 2020, 56 (02) : 283 - 305
  • [5] New Turan Type Bounds for Johnson Graphs
    Dubinin, N. A.
    PROBLEMS OF INFORMATION TRANSMISSION, 2021, 57 (04) : 373 - 379
  • [6] Inverting the Turan problem
    Briggs, Joseph
    Cox, Christopher
    DISCRETE MATHEMATICS, 2019, 342 (07) : 1865 - 1884
  • [7] The spectral Turan problem about graphs of given size with forbidden subgraphs
    Rehman, Amir
    Pirzada, S.
    AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2025, 22 (01) : 91 - 93
  • [8] On the Turan Number of Theta Graphs
    Zhai, Mingqing
    Fang, Longfei
    Shu, Jinlong
    GRAPHS AND COMBINATORICS, 2021, 37 (06) : 2155 - 2165
  • [9] An Extremal Property of Turan Graphs
    Lazebnik, Felix
    Tofts, Spencer
    ELECTRONIC JOURNAL OF COMBINATORICS, 2010, 17 (01):
  • [10] Some results on k-Turan-good graphs
    Qian, Bingchen
    Xie, Chengfei
    Ge, Gennian
    DISCRETE MATHEMATICS, 2021, 344 (09)
12345