Graphs with n vertices, m edges, and with smallest sum of squares of the vertex degrees are characterized. These are the graphs in which the degree of any vertex is equal to either [2 m / n ] or [2 m / n ]. Such graphs exist for all n ? 1 and 0 ? m ? n ( n -1)/2.
展开▼
机译:描绘了具有n个顶点,m个边且顶点度的平方和最小的图。这些是其中任何顶点的度等于[2 m / n]或[2 m / n]的图。所有n个图都存在这样的图。 1和0?米n(n -1)/ 2。
展开▼