A minimax problem for graphs and its relation to generalized doubly stochastic matrices

1 April 1990

journal article
research article
Published by Taylor & Francis in Linear and Multilinear Algebra

Vol. 27 (1) , 1-23
https://doi.org/10.1080/03081089008817989

Abstract

A general approach to a class of minimax problems for graphs is formulated. Let Gbe a simple graph 8(G) the set of all nonnegative valuations Cis of the set of edges of Gthe sum of the valuations of which is equal to the number of edges. Properties of the minimum for Cε 8(G)h(G) of the maximum eigenvalue of the Laplacian of G(endowed by the valuation C) are investigated, in particular, for bipartite graphs and trees. For bipartite giaphs, a close relationship with t he generalized doubly stochastic matrices is shown.

Keywords

This publication has 3 references indexed in Scilit:

Absolute algebraic connectivity of trees
Linear and Multilinear Algebra, 1990
Algebraic connectivity of graphs
Czechoslovak Mathematical Journal, 1973
Integer Programming: Methods, Uses, Computations
Management Science, 1965