Maximum variances and minimum statuses of connected Weighted Graphs

Abstract

Let G be a connected graph. For a permutation of V(G), the variance v(G)(phi) due to phi is the sum of d(G)(x,phi(x)) (x is an element of V(G)). The maximum variance Mv(G) of G is the maximum of v(G)(phi) (phi is a permutation of V(G)). For a vertex x in G, the status s(G)(x) of x is the sum of d(G)(x,y) (y is an element of V(G)). The minimum status ms(G) of G is the minimum of s(G)(x) (x is an element of 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 connected 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.