Digraphs with a fixed number of edges and vertices, having a maximal number of walks of length 2

2008/04/29 by Jan Snellman, Snellman, Jan
Mathematics · #Algebraic structures and combinatorial models #Combinatorics (math.CO) #Commutative Algebra and Its Applications #FOS: Mathematics #Graph theory and applications #Rings and Algebras (math.RA)

paper · pdf · doi:10.48550/arxiv.0804.4655

openalex publication_date 2008/04/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Inspired by the work of Backelin on non-commutative correspondences to Macaulay's theorem of the growth of the Hilbert series of affine algebras, we study embedding dimension dependant versions of his degree 2 to degree 3 result. In graph-theoretical terms, we study the following question: what is the maximal number of directed walks of length 2 in a digraph with (k) edges and (n) vertices? The problem can also be formulated as follows: maximize (< λ, λ^T >) when (λ) is a partition of (k), contained in an (n × n) box. We show that for mild restrictions on (n), optimal digraphs are the ``stars of saturated stars''.

Related

• Extremal digraphs avoiding distinct walks of length 3 with the same endpoints
• A note on extremal digraphs containing at most t walks of length k with the same endpoints
• The Turan problems of directed paths and cycles in digraphs
• Turán problems for digraphs avoiding distinct walks of a given length with the same endpoints
• Two results on the digraph chromatic number