Some minimax problems for graphs (Q1309451): Difference between revisions

Generalization of a characteristic \(\omega(G)\) of \(G\) to \(\omega(G_ C)\) for the class of edge-valuated graphs \(G_ C=(V,E,C)\), where \(C\) is a valuation of the set of edges \(E\) by nonnegative numbers with the sum \(| E |\), was dealt with. A characteristic \(\hat\omega(G)\) was obtained by minimizing or maximizing \(\omega(G_ C)\) over all \(C\). Absolute algebraic connectivity of trees was discussed as a strengthening of the results given by the author previously, see [Linear Multilinear Algebra 26, No. 1/2, 85-106 (1990; Zbl 0737.05043)]. It was shown that for a tree \(T\) with \(n\) vertices \(12/n(n+1)\leq \hat a(T)\leq 1\), where \(\hat a(T)\) is a rational number of the form \(n(n-1)/C\) where \(C\) is an integer satisfying \(n(n-1) \leq C \leq {1 \over 12} n^ 2(n^ 2-1)\). Formulas were derived for the absolute diameter and the absolute radius of a graph.