Digraphs with a fixed number of edges and vertices, having a maximal number of walks of length 2
From MaRDI portal
Publication:6209322
arXiv0804.4655MaRDI QIDQ6209322FDOQ6209322
Authors: J. E. Snellman 
Publication date: 29 April 2008
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 (< lambda, lambda^T >) when (lambda) is a partition of (k), contained in an (n imes n) box. We show that for mild restrictions on (n), optimal digraphs are the ``stars of saturated stars.
This page was built for publication: Digraphs with a fixed number of edges and vertices, having a maximal number of walks of length 2
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6209322)
