On the Number of 4-Edge Paths in Graphs With Given Edge Density. (23rd December 2016)

• Record Type: Journal Article
• Authors: NAGY, DÁNIEL T.
• Is Part Of: Combinatorics, probability and computing. Volume 26:Number 3(2017:May)
• Page Start: 431
• Page End: 447
• Publication Date: 2016-12-23
• Subjects: Primary 05C35; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548316000389
• Languages: English
• ISSNs: 0963-5483

Abstract

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.