Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A Turán-Type Problem on Distances in Graphs

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aigner M.: Turán’s graph theorem. Am. Math. Monthly 102, 808–816 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  2. Ahlswede R., Katona G.O.H.: Graphs with maximal number of adjacent pairs of edges. Acta Math. Acad. Sci. Hungar 32, 97–120 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  3. Alon N.: On the number of subgraphs of prescribed type of graphs with a given number of edges. Israel J. Math. 38, 116–130 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  4. Alon N.: On the number of certain subgraphs contained in graphs with a given number of edges. Israel J. Math. 53, 97–120 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  5. Bollobás B., Erdős P.: Graphs of extremal weights. Ars. Combin. 50, 225–233 (1998)

    MathSciNet  MATH  Google Scholar 

  6. Bollobás B., Sarkar A.: Paths in graphs. Stud. Sci. Math. Hungar 38, 115–137 (2001)

    MATH  Google Scholar 

  7. Bollobás B., Sarkar A.: Paths of length four. Discrete Math. 265, 357–363 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  8. Bollobás B., Tyomkyn M.: Walks and paths in trees. J. Graph Theory 70(1), 54–66 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  9. Byer O.D.: Maximum number of 3-paths in a graph. Ars. Combin. 61, 73–79 (2001)

    MathSciNet  MATH  Google Scholar 

  10. Csikvári P.: On a poset of trees. Combinatorica 30(2), 125–137 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  11. Füredi Z.: Graphs with maximum number of star-forests. Stud. Sci. Math. Hungar 27, 403–407 (1992)

    MATH  Google Scholar 

  12. Katz M.: Rearrangements of (0–1) matrices. Israel J. Math. 9, 53–71 (1971)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Pure Mathematics and Mathematical Statistics, Centre for Mathematical Sciences, University of Cambridge, Wilberforce Road, Cambridge, CB3 0WB, UK

    Mykhaylo Tyomkyn

  2. Department of Mathematical Sciences, University of Memphis, Memphis, TN, 38152-3240, USA

    Andrew J. Uzzell

Authors
  1. Mykhaylo Tyomkyn
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Andrew J. Uzzell
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Andrew J. Uzzell.

Additional information

A. J. Uzzell’s work was partially supported by NSF grant DMS-0505550.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Tyomkyn, M., Uzzell, A.J. A Turán-Type Problem on Distances in Graphs. Graphs and Combinatorics 29, 1927–1942 (2013). https://doi.org/10.1007/s00373-012-1225-4

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-012-1225-4

Keywords

Mathematics Subject Classification (2000)

Search

Navigation