Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-25T18:27:54.808Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Number of 4-Edge Paths in Graphs With Given Edge Density

Part of: Graph theory

Published online by Cambridge University Press:  23 December 2016

DÁNIEL T. NAGY
DÁNIEL T. NAGY*
Affiliation:
Eötvös Loránd University, Egyetem tér 1-3, Budapest 1053, Hungary (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We investigate the number of 4-edge paths in graphs with a given number of vertices and edges, proving an asymptotically sharp upper bound on this number. The extremal construction is the quasi-star or the quasi-clique graph, depending on the edge density. An easy lower bound is also proved. This answer resembles the classic theorem of Ahlswede and Katona about the maximal number of 2-edge paths, and a recent theorem of Kenyon, Radin, Ren and Sadun about k-edge stars.

MSC classification

Primary: 05C35: Extremal problems
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 3 , May 2017 , pp. 431 - 447
Copyright
Copyright © Cambridge University Press 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Ahlswede, R. and Katona, G. O. H. (1978) Graphs with maximal number of adjacent pairs of edges. Acta Math. Acad. Sci. Hungar. 32 97–120.Google Scholar
[2] Alon, N. (1981) On the number of subgraphs of prescribed type of graphs with a given number of edges. Israel J. Math. 38 116–130.CrossRefGoogle Scholar
[3] Alon, N. (1986) On the number of certain subgraphs contained in graphs with a given number of edges. Israel J. Math. 53 97–120.Google Scholar
[4] Bollobás, B. and Sarkar, A. (2001) Paths in graphs. Studia Sci. Math. Hungar. 38 115–137.Google Scholar
[5] Bollobás, B. and Sarkar, A. (2003) Paths of length four. Discrete Math. 265 357–363.Google Scholar
[6] Füredi, Z. (1992) Graphs with maximum number of star-forests. Studia Sci. Math. Hungar. 27 403–407.Google Scholar
[7] Kenyon, R., Radin, C., Ren, K. and Sadun, L. Multipodal structure and phase transitions in large constrained graphs. arXiv:1405.0599 Google Scholar
[8] Lovász, L. (2012) Large Networks and Graph Limits, AMS.Google Scholar
[9] Nikiforov, V. (2011) The number of cliques in graphs of given order and size. Trans. Amer. Math. Soc. 363 1599–1618.CrossRefGoogle Scholar
[10] Razborov, A. A. (2008) On the minimal density of triangles in graphs. Combin. Probab. Comput. 17 603–618.Google Scholar
[11] Reiher, C. (2016) The clique density theorem. Annals of Mathematics 184 683–707.CrossRefGoogle Scholar