Maximum variances and minimum statuses of connected Weighted Graphs
Let G be a connected graph. For a permutation φ of VG), 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 SGX) 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. , journal=Utilitas Mathematica , author=Lin, Chiang and Tsai, Wei-Han and Shang, Jen-Ling and Lee, Ming-Ju, year=2017, month=Sep.