×

Permutation inequalities. (English) Zbl 1291.05019

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

Software:

PlanetMath
PDFBibTeX XMLCite
Full Text: DOI