Maximizing the sum of the squares of the degrees of a graph

@article{citeulike:1907530, abstract = {Let G=(V,E) be a simple graph with n vertices, e edges, and vertex degrees d1,d2,...,dn. Also, let d1, dn be, respectively, the highest degree and the lowest degree of G and mi be the average of the degrees of the vertices adjacent to vertex vi[set membership, variant]V. It is proved thatwith equality if and only if G is an Sn graph (K1,n-1[subset of or equal to]Sn[subset of or equal to]Kn) or a complete graph of order n-1 with one isolated vertex. Using the above result we establish the following upper bound for the sum of the squares of the degrees of a graph G:with equality if and only if G is a star graph or a regular graph or a complete graph Kd1+1 with n-d1-1 isolated vertices. A comparison is made to another upper bound on [summation operator]i=1n di2, due to de Caen (Discrete Math. 185 (1998) 245). We also present several upper bounds for [summation operator]i=1n di2 and determine the extremal graphs which achieve the bounds.}, author = {Das, Kinkar C. }, citeulike-article-id = {1907530}, doi = {http://dx.doi.org/10.1016/j.disc.2004.04.007}, journal = {Discrete Mathematics}, keywords = {graph\_theory}, month = {August}, number = {1-3}, pages = {57--66}, posted-at = {2007-11-13 14:34:29}, priority = {0}, title = {Maximizing the sum of the squares of the degrees of a graph}, url = {http://dx.doi.org/10.1016/j.disc.2004.04.007}, volume = {285}, year = {2004} }

TY - JOUR ID - citeulike:1907530 L3 - citeulike-article-id:1907530 TI - Maximizing the sum of the squares of the degrees of a graph JF - Discrete Mathematics VL - 285 IS - 1-3 SP - 57 EP - 66 N2 - Let G=(V,E) be a simple graph with n vertices, e edges, and vertex degrees d1,d2,...,dn. Also, let d1, dn be, respectively, the highest degree and the lowest degree of G and mi be the average of the degrees of the vertices adjacent to vertex vi[set membership, variant]V. It is proved thatwith equality if and only if G is an Sn graph (K1,n-1[subset of or equal to]Sn[subset of or equal to]Kn) or a complete graph of order n-1 with one isolated vertex. Using the above result we establish the following upper bound for the sum of the squares of the degrees of a graph G:with equality if and only if G is a star graph or a regular graph or a complete graph Kd1+1 with n-d1-1 isolated vertices. A comparison is made to another upper bound on [summation operator]i=1n di2, due to de Caen (Discrete Math. 185 (1998) 245). We also present several upper bounds for [summation operator]i=1n di2 and determine the extremal graphs which achieve the bounds. KW - graph_theory AU - Das, Kinkar PY - 2004/08/06/ UR - http://dx.doi.org/10.1016/j.disc.2004.04.007 ER -