Some minimax problems for graphs
type: Item
instance of: scholarly article
title: Some minimax problems for graphs
zbMATH Open document ID: 0786.05023
DOI: 10.1016/0012-365X(93)90538-5
author: Miroslav Fiedler
published in: Discrete Mathematics
publication date: 1993-12-20T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 473116
zbMATH Keywords: distance
zbMATH Keywords: connectivity
zbMATH Keywords: trees
zbMATH Keywords: diameter
zbMATH Keywords: radius
MaRDI profile type: Publication
cites work: Q4097336
cites work: Q3356330
cites work: Absolute algebraic connectivity of trees
cites work: A minimax problem for graphs and its relation to generalized doubly stochastic matrices
cites work: An extremal problem for the spectral radius of a graph
cites work: Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph
cites work: Q5202209
description: scientific article; zbMATH DE number 473116