Ioan Tomescu: Minimizing vertex-degree function index for $k$-generalized quasi-trees, 265-272

Abstract:

In this paper the problem of minimizing the vertex-degree function index $H_{f}(G)$ for $k$-generalized quasi-trees of order $n$ is solved for $k\geq 1$ and $n\geq 3k$ if the function $f$ is strictly increasing and strictly convex. The extremal graph is a cycle $C_n$ for $k=1$ and $n\geq 3$. For $k=2$ and $n\geq 6$ there are two families of extremal graphs depending upon the case when the inequality $f(3)+3f(1)<4f(2)$ is fulfilled or not. For $k\geq 3$ and $n\geq 3k$ there is a single family of extremal graphs and the number of pairwise non-isomorphic graphs of this family equals $1+\lfloor (n-3k)/2 \rfloor$.

Key Words: Vertex-degree function index, $k$-generalized quasi-tree, Jensen's inequality, majorization, Muirhead's Lemma.

2020 Mathematics Subject Classification: Primary 05C35; Secondary 05C75, 05C09.

Download the paper in pdf format here.