Maximum variances and minimum statuses of connected Weighted Graphs
Abstract
Let G be a connected graph. For a permutation φ of V{G), the variance vG(φ) due to φ is the sum of do(x,<p(x)) (x ϵ V(G)). The maximum variance Mv(G) of G is the maximum of VG(φ) (φ is a permutation of V(G)). For a vertex x in G, the status SG{X) of X is the sum of dG(x, y) (y ϵ V(G)). The minimum status ms(G) of G is the minimum of SG(X) (x ϵ V(G)). A vertex x in G is said to be a vertex with 1/2-property, if |V(G′)| ≤ 1/2|V(G)| for every component G′ of G-x. A weighted graph (G, w) is a graph G with a weight function w defined on E(G). The notions of maximum variance and minimum status are extended to connected weighted graphs. Let Mv(G, w) and ms(G, w) denote the maximum variance and the minimum status, respectively, of a connected weighted graph (G, w). In section 2, we prove that if a con-nected weighted graph (G, w) contains a vertex with 1/2-property, then Mv(G, w) - 2ms(G, w). We also give a criterion of bipartite graphs in terms of variance, and investigate the variance spectrum of a connected graph which contains a vertex with 1/2-property. In section 3, we obtain the formulas for the maximum variance and the minimum status, respectively, of the Cartesian product of two connected weighted graphs.
