Hostname: page-component-745bb68f8f-s22k5 Total loading time: 0 Render date: 2025-02-06T20:00:12.144Z 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: dani.t.nagy@gmail.com)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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 

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