Title:
Graphs with Minimum Vertex-Degree Function-Index for Convex Functions
Authors:
Zhoukun Hu, Xueliang Li, Danni Peng
Volume
88
Issue
3
Year
2022
Pages
521-533
Abstract An $$(n,m)$$-graph is a graph with $$n$$ vertices and $$m$$ edges. The vertex-degree function-index $$H_f(G)$$ of a graph $$G$$ is defined as $$H_f(G)=\sum_{v\in V(G)} f(d(v))$$, where $$f$$ is a real function. Recently, Tomescu considered the upper bound of $$H_f(G)$$ and got the connected $$(n,m)$$-graph $$G$$ with $$m\geq n$$ which maximizes $$H_f(G)$$ if $$f(x)$$ is strictly convex with two special properties. He also characterized all $$(n,m)$$-graphs $$G$$ with $$1\leq m\leq n$$ satisfying that $$H_f(G)\leq f(m)+mf(1)+(n-m-1)f(0)$$ if \)f(x)\) is strictly convex and differentiable and its derivative is strictly convex. In this paper, we will consider the lower bound of $$H_f(G)$$ and show that every $$(n,m)$$-graph with $$1\leq m\leq n(n-1)/2$$ satisfies that $$H_f(G)\geq rf(k+1)+(n-r)f(k)$$ if $$f(x)$$ is strictly convex, where $$k=\lfloor 2m/n \rfloor$$ and $$r=2m-nk$$. Moreover, the equality holds if and only if $$G\in \mathcal{G}(n,m)$$, where $$\mathcal{G}(n,m)$$ is the family of all $$(n,m)$$-graphs $$G$$ satisfying that the vertex-degree $$d(v)\in \{\lfloor \frac{2m}{n} \rfloor,\lceil \frac{2m}{n} \rceil \}$$ for all $$v\in V(G)$$. Under the same condition on $$f$$ we also obtain a result for the minimum of $$H_f(G)$$ among all connected $$(n,m)$$-graphs. It is easy to see that if $$f(x)$$ is strictly concave, we can get the maximum case for $$H_f(G)$$.