Kovič, Jurij Permutation inequalities. (English) Zbl 1291.05019 Math. Inequal. Appl. 17, No. 2, 419-429 (2014). Summary: We formulate and solve some special cases of the following (in general NP-hard) extremal problem: “ Given a graph \(G\) (or a hypergraph \(H\) ), label its vertices with given different n non-negative numbers \(a_1\geqslant a_2 \geqslant \ldots \geqslant a_n\geqslant 0\) in such a way that the sum of the products of labels in adjacent vertices \(f = \sum a_ia_j\) will be maximal (or minimal)”. Solving this problem for some special families of graphs (e.g. paths, trees and stars) we obtain examples of “permutation inequalities” \(f_{\min}\leqslant f \leqslant f_{\max}\). MSC: 05A20 Combinatorial inequalities 05C22 Signed and weighted graphs 05C78 Graph labelling (graceful graphs, bandwidth, etc.) 26D15 Inequalities for sums, series and integrals Keywords:inequality; permutation; rearrangement; bilinear function; multilinear function; labeled graph; hypergraph Software:PlanetMath PDFBibTeX XMLCite \textit{J. Kovič}, Math. Inequal. Appl. 17, No. 2, 419--429 (2014; Zbl 1291.05019) Full Text: DOI