×

Graphs of extremal weights. (English) Zbl 0963.05068

The authors consider the graph weight \(w_\alpha (G)=\sum _{e\in E(G)}w_{\alpha }(e)\), where \(\alpha \neq 0\) is fixed and \(w_{\alpha }(e)=w_{\alpha }(\{x,y\})=(d(x)d(y))^\alpha \) with \(d(x)\) being the degree of \(x\). It is proved that for the Randić weight \(\alpha =-1/2\) (in the first definition in the article the “\(-\)” is missing), if \(G\) has order \(n\) and no isolated vertex then \(w_{-1/2}(G)\geq \sqrt {n-1}\), with equality only for stars. It is also proved that for every \(G\) with \(m\) edges one has \(w_{\alpha }(G)\leq m(((8m+1)^{1/2}-1)/2)^{2\alpha }\) for \(0<\alpha \leq 1\) and the opposite inequality for \(-1\leq \alpha <0\), with equality attained iff \(G\) is a complete graph plus some isolated vertices. Further results are given.

MSC:

05C35 Extremal problems in graph theory
05C07 Vertex degrees
PDF BibTeX XML Cite