Ioan Tomescu

Faculty of Mathematics and Computer Science, Bucharest University, Str. Academiei, 14, 010014 Bucharest, Romania

ioan@fmi.unibuc.ro

In this paper, the vertex-degree function index H^f (G) is considered when function f(x) belongs to four classes of functions determined by the following properties: strictly convex versus strictly concave and strictly increasing versus strictly decreasing. Quasi-unicyclic graphs of given order (or of given order and fixed number of pendant vertices) extremal relatively to vertex-degree function index for these classes of functions are determined. These conditions are fulfilled by several topological indices of graphs.

Keywords: quasi-unicyclic graphs, vertex-degree function index, strictly convex/strictly concave function, strictly increasing/strictly decreasing function, Jensen inequality Mathematics Subject Classification: 05C35, 05C75, 05C09

DOI: 10.5614/ejgta.2023.11.1.4

1. Introduction

Let G be a simple graph having V (G) and E(G) the vertex set and the edge set of G, respectively. For any v ∈ V (G), we denote by d(v) the degree of v and by δ(G) the minimum degree minv∈^V (G) d(v). The set of neighbors of v is denoted by N(v). A vertex with degree one will also be referred as a pendant vertex and a vertex adjacent to all other vertices as a universal vertex. Suppose that V (G) = {v1, v2, . . . , vn} and the degree of vertex vⁱ equals d(vi) = dⁱ for i = 1, 2, . . . , n, then (d1, d2, . . . , dn) is called the degree sequence of G. We always will enumerate the degrees in non-increasing order, i.e., d¹ ≥ d² ≥ . . . ≥ dn.

Received: 26 June 2022, Revised: 27 February 2023, Accepted: 4 March 2023.

For graph G and a subset X of V (G), G − X denotes the graph obtained from G by removing the vertices of X and all edges incident to any of them. In particular, when X consists of only one vertex v, G − {v} is denoted by G − v. Similar notation is G − uv, where uv ∈ E(G) and G + uv, where uv /∈ E(G).

For two vertex-disjoint graphs G and H, the join G ∨ H is obtained by joining by edges each vertex of G to all vertices of H.

K1,n−1, Pⁿ and Cⁿ will denote the star, the path and the cycle on n vertices, respectively. K1,n−¹ + e is deduced from K1,n−¹ by inserting a new edge between two pendant vertices of K1,n−1. The wheel graph of order n is Cn−¹ ∨ K1.

A unicyclic graph G of order n is connected and has n edges. It consists of a cycle Cr, where 3 ≤ r ≤ n and some vertex-disjoint trees having each a vertex common with Cr, which will be called pendant trees. We call G a quasi-unicyclic graph if there is v ∈ V (G) such that G − v is a unicyclic graph; v is called a quasi-vertex. It is clear that every unicyclic graph which is not a cycle has a pendant vertex, so it is also a quasi-unicyclic graph.

Every unicyclic graph contains a cycle C^r with r ≥ 3, those vertices are not pendant. Thus the number of pendant vertices in a unicyclic graph of order n is 0 ≤ p ≤ n − 3. If a quasi-unicyclic graph has a universal vertex, then the number p of pendant vertices verifies 0 ≤ p ≤ n − 4. If G is a quasi-unicyclic graph then δ(G) ≤ 3 since by deleting a quasi-vertex v the graph G − v is unicyclic and has δ(G − v) ≤ 2.

For other notations and definitions in graph theory, we refer [13].

The first Zagreb index M1(G) [5] is defined as M1(G) = P v∈V (G) d(v) 2 . The general first Zagreb index (sometimes referred as "zeroth-order general Randic index" [6]), denoted by ´ ⁰Rα(G) was defined [7] as ⁰Rα(G) = P v∈V (G) d(v) α , where α is a real number, α ̸∈ {0, 1}. For α = 2 it is the first Zagreb index M1(G).

Extremal results concerning the first Zagreb index for quasi-unicyclic graphs were obtained in [2].

Todeschini et al. [8] introduced a variant of Zagreb indices which are called the first and second multiplicative Zagreb indices, and they are defined as:

\[\Pi_1(G) = \prod_{u \in V(G)} d(u)^2, \ \Pi_2(G) = \prod_{uv \in E(G)} d(u)d(v) = \prod_{u \in V(G)} d(u)^{d(u)}.\]

A generalized form of multiplicative Zagreb indices, which are called the first and second general multiplicative Zagreb indices was proposed by Vetr´ık and Balachandran [10]. For a graph G, they are defined as:

\[P_1^{\alpha}(G) = \prod_{u \in V(G)} d(u)^{\alpha}, \quad P_2^{\alpha}(G) = \prod_{uv \in E(G)} (d(u)d(v))^{\alpha} = \prod_{u \in V(G)} d(u)^{\alpha d(u)},\]

where α ∈ R\{0}.

In [10] the minimum and maximum general multiplicative Zagreb indices of trees with given order and number of branching vertices, pendant vertices or segments were obtained. Extremal results concerning general multiplicative Zagreb indices for unicyclic graphs were obtained in [1], for trees and unicyclic graphs with given matching number in [11], for trees and quasi-trees with

perfect matchings and with given order and number of pendant vertices in [3], for quasi-unicyclic graphs with given order, fixed number of pendant vertices and with perfect matchings in [4].

The sum lordeg index is one of the Adriatic indices introduced in [12] and it is defined by SL(G) = P v∈V (G) d(v) p ln d(v) = X v∈V (G):d(v)≥2 d(v) p ln d(v).

The vertex-degree function index H^f (G) was defined in [14] as

\[H_f(G) = \sum_{v \in V(G)} f(d(v))\]

for a function f(x) defined on positive real numbers. The problem of minimizing vertex-degree function index H^f (G) for k-generalized quasi-unicyclic graphs of given order was solved in [9] for functions f(x) which are strictly increasing and strictly convex.

In this paper we will impose to function f(x) to be strictly convex or strictly concave, and strictly increasing or strictly decreasing, respectively which yields four disjoint sets of functions f(x).

The rest of the paper is organized as follows. In Section 2, we deduce some preliminary results. In Section 3, we solve the problem of maximizing or minimizing the vertex-degree function index H^f (G) for quasi-unicyclic graphs G with given order if f(x) belongs to each of these four sets and characterize the extremal graphs.

2. Preliminary results

In what follows we shall use many times a well known property of strictly convex functions:

Lemma 2.1. Let y > 0 and x ≥ y + 2. If function f(x) is strictly convex, then

\[f(x) + f(y) > f(x - 1) + f(y + 1).\]

In the case of strictly concave functions this inequality must be reversed.

Proof. The function f(x) being strictly convex, φ(x) = f(x + 1) − f(x) is a strictly increasing function. Since x − 1 ≥ y + 1 > y it follows that φ(x − 1) > φ(y), or f(x) − f(x − 1) > f(y + 1) − f(y).

Lemma 2.2. Let f(x) be a strictly convex function defined on positive real numbers. Then

\[f(n) - (n-2)f(3) + (n-3)f(2) > 0\] (1)

for every n ∈ N, n ≥ 4.

Proof. f(x) being strictly convex, then for every x1, x² and λ1, λ² > 0 with λ¹ + λ² = 1, we have Jensen inequality: λ1f(x1) + λ2f(x2) > f(λ1x¹ + λ2x2). If we choose x¹ = n, x² = 2, λ¹ = 1/(n − 2), λ² = (n − 3)/(n − 2), this yields (1).

Note that a similar result holds by replacing strictly convex by strictly concave and by reversing inequality in (1).

Lemma 2.3. Let \(n, p \in \mathbb{N}\), \(n \ge 4\) and \(1 \le p \le n-3\). If function f(x) is strictly convex (concave), then g(n,p) = f(p+2) + (n-p-1)f(2) + pf(1) is strictly increasing (strictly decreasing, respectively) in p.

Proof. If f(x) is strictly convex, then g(n, p+1) > g(n, p) is equivalent to f(p+3) - f(p+2) - f(2) + f(1) > 0, which is true by Lemma 2.1.

For integers n,m such that \(n \geq 1\) and \(m \geq n\) denote by \(D_{n,m}\) the set of n-tuples of integers \(\mathbf{x} = (x_1, x_2, \dots, x_n)\) such that \(x_1 \geq x_2 \geq \dots \geq x_n \geq 1\) and \(\sum_{i=1}^n x_i = m\). Let the function \(F(\mathbf{x}) = \sum_{i=1}^n f(x_i)\). If f(x) is a strictly convex function, then by Lemma 2.1 the minimum of \(F(\mathbf{x})\) is reached if and only if \(|x_i - x_j| \leq 1\) for every \(1 \leq i < j \leq n\), or equivalently, if and only if \(x_1 + x_2 + \dots + x_n\) is an equipartition of \(x_1 + x_2 + \dots + x_n\) is an equipartition of \(x_1 + x_2 + \dots + x_n\) is unique. A similar result follows for the maximum of \(x_1 + x_2 + \dots + x_n = n\) is unique. A similar result follows for the maximum of \(x_1 + x_2 + \dots + x_n = n\) is strictly concave. If \(x_1 + x_2 + \dots + x_n = n\) is a greatest as possible and an analogous result holds for the minimum of \(x_1 + x_2 + \dots + x_n = n\) is a greatest as possible and an analogous result holds for the minimum of \(x_1 + x_2 + \dots + x_n = n\) is a greatest as possible and an analogous result holds for the minimum of \(x_1 + x_2 + \dots + x_n = n\) is a greatest as possible and an analogous result holds for the minimum of \(x_1 + x_2 + \dots + x_n = n\) is a greatest as possible and an analogous result holds for the minimum of \(x_1 + x_2 + \dots + x_n = n\) is a greatest as possible and an analogous result holds for the minimum of \(x_1 + x_2 + \dots + x_n = n\) is a greatest as possible and an analogous result holds for the minimum of \(x_1 + x_2 + \dots + x_n = n\) is an equipartition of \(x_1 + x_2 + \dots + x_n = n\) is an equipartition of \(x_1 + x_2 + \dots + x_n = n\) is an equipartition of \(x_1 + x_2 + \dots + x_n = n\) in the first component of \(x_1 + x_2 + \dots + x_n = n\) is an equipartition of \(x_1 + x_2 + \dots + x_n = n\) in the first component of \(x_1 + x_2 + \dots + x_n = n\) is an equipartition of \(x_1 + x_2 + \dots + x_n = n\) in the first component of \(x_1 + x_2 + \dots + x_n = n\) in the first component of \(x_1 + x_2 + \dots + x_n = n\) in the first component of \(x_1 + x_2 + \dots + x_n = n\) in the first component of \(x_1 + x_2 + \dots + x_n = n\) in the first component of \(x_1\)

Lemma 2.4. Let G be a unicyclic graph of order n with p pendant vertices, where \(n \ge 4\), \(1 \le p \le n-3\) and f(x) be a strictly concave function. Then

\[H_f(G) \ge f(p+2) + (n-p-1)f(2) + pf(1)\]

and extremal graphs consist of one cycle and p paths attached to a unique vertex of this cycle.

Proof. It follows that the degree sequence of G has the form \((d_1, d_2, \ldots, d_{n-p}, 1, \ldots, 1)\), where \(d_1 \geq d_2 \geq \cdots \geq d_{n-p} \geq 2\). Then \(\min H_f(G)\) is equal to the minimum of \(F(\mathbf{x})\), where \(\mathbf{x} \in D_{n,2n}\) and has the last p components equal to 1 if this minimum is reached for a graphical sequence. This happens only if the degree sequence of G is \((p+2, 2^{n-p-1}, 1^p)\), where the exponent indicates multiplicity. This degree sequence has many graphical realizations, which may be characterized as follows: the class of extremal graphs consists of cycles with p paths attached to the same vertex of the cycle.

Note that a similar result holds by replacing strictly concave by strictly convex, and minimum by maximum, respectively.

3. Main results

Theorem 3.1. Let G be a quasi-unicyclic graph of order \(n \ge 4\). If f(x) is strictly concave and strictly increasing (strictly convex and strictly decreasing, respectively), then minimum (maximum, respectively) of \(H_f(G)\) equals

\[f(n-1) + 2f(2) + (n-3)f(1)\].

In this case, the extremal graph is unique, namely \(K_{1,n-1} + e\).

Proof. Suppose that f(x) is strictly concave and strictly increasing. Let v be a quasi-vertex such that G − v is a unicyclic graph. If H^f (G) is minimum it follows that d(v) = 1, which implies that G is a unicyclic graph with p pendant vertices, where 1 ≤ p ≤ n − 3. From Lemmas 2.3 and 2.4 we get that H^f (G) is minimum only for p = n − 3, when G = K1,n−¹ + e. The proof is similar if f(x) is strictly convex and strictly decreasing.

Theorem 3.2. Let G be a quasi-unicyclic graph of order n ≥ 4. If f(x) is strictly concave and strictly increasing (strictly convex and strictly decreasing, respectively), then maximum (minimum, respectively) of H^f (G) equals

\[f(n-1) + (n-1)f(3).\]

Extremal graph is unique, the wheel graph Cn−¹ ∨ K1.

Proof. Suppose that f(x) is strictly concave and strictly increasing. The proof is by induction on n ≥ 4. For n = 4 since f(x) is strictly increasing it follows that H^f (G) is maximum only for G = C³ ∨ K¹ = K4. Let n ≥ 5 and suppose that the property is true for all unicyclic graphs of order n − 1. If G is a quasi-unicyclic graph of order n which maximizes H^f (G) and v is a quasi-vertex of G, since f(x) is strictly increasing it follows that d(v) = n − 1 and v is unique with this property. We also get δ(G) ∈ {2, 3}. If δ(G) = 3, then G = Cn−¹ ∨ K¹ and we are done. Otherwise δ(G) = 2, therefore there exists u ∈ V (G) having d(u) = 2. Let w be the vertex adjacent to u which is different from v. We get d(w) ≥ 3 since otherwise G − v would not be connected and G − u is a quasi-unicyclic graph of order n − 1. By the induction hypothesis we deduce:

\[H_f(G) = H_f(G - u) + f(2) + f(n - 1) + f(d(w)) - f(n - 2) - f(d(w) - 1)\] \[\leq f(2) + f(n - 1) + f(d(w)) - f(d(w) - 1) + (n - 2)f(3).\]

We have

\[f(2) + f(n-1) + f(d(w)) - f(d(w) - 1) + (n-2)f(3) \le f(n-1) + (n-1)f(3)\]

since this is equivalent to f(d(w)) + f(2) ≤ f(d(w) − 1) + f(3). By Lemma 2.1 equality holds only if d(w) = 3 and G − u = Cn−² ∨ K1. But G − u = Cn−² ∨ K¹ implies that d(w) = 4, a contradiction. It follows that if δ(G) = 2 then G cannot be extremal. This concludes the proof. The proof is similar when f(x) is strictly convex and strictly decreasing.

Theorem 3.3. Let G be a quasi-unicyclic graph of order n ≥ 4. If f(x) is strictly convex and strictly increasing (strictly concave and strictly decreasing, respectively), then minimum (maximum, respectively) of H^f (G) equals

\[f(3) + (n-2)f(2) + f(1).\]

There are n − 3 extremal graphs, which consists each of a cycle C^k and a path Pn−k+1 attached to a vertex of the cycle for 3 ≤ k ≤ n − 1.

Proof. Let f(x) be strictly convex and strictly increasing and G be a unicyclic graph such that H^f (G) is minimum. If v is a quasi-vertex then d(v) = 1. It follows that G is a unicyclic graph which is not a cycle. If G has exactly one pendant vertex, the theorem is true. Otherwise, G has at least two pendant vertices and a unique cycle Ck. Let t be a pendant vertex different from v, which belongs to a pendant tree attached to a vertex r ∈ V (C). We get d(r) ≥ 3. Denote by v¹ and v² the vertices adjacent with r on C and let G¹ = G − rv¹ + tv1. G¹ is also a quasi-unicyclic graph of order n which has a quasi-vertex which is pendant. We deduce

\[H_f(G_1) = H_f(G) + f(d(r) - 1) - f(d(r)) + f(2) - f(1) < H_f(G),\]

a contradiction because by Lemma 2.1 f(d(r)) + f(1) > f(d(r) − 1) + f(2), f(x) being strictly convex and d(r) ≥ 3. This concludes the proof.

A similar proof can be done when f(x) is strictly concave and strictly decreasing.

Theorem 3.4. If G is a quasi-unicyclic graph of order n ≥ 4 and f(x) is strictly convex and strictly increasing (strictly concave and strictly decreasing, respectively), then maximum (minimum, respectively) of H^f (G) equals

\[2f(n-1) + 2f(3) + (n-4)f(2).\]

Extremal graph is unique, namely (K1,n−² + e) ∨ K1.

Proof. Let f(x) be strictly convex and strictly increasing and G be a unicyclic graph such that H^f (G) is maximum. Since f(x) is strictly increasing it follows that there is a quasi-vertex v which is a universal vertex. The proof is by induction on n ≥ 4. For n = 4 we get that G − v = C3, G = K⁴ and the proof was done. Let n ≥ 5 and suppose that the property is valid for all quasiunicyclic graphs of order n − 1.

We have two cases to consider: Case 1. δ(G) = 3 and Case 2. δ(G) = 2.

Case 1. If δ(G) = 3 it follows that G = Cn−¹ ∨ K1. We get

\[H_f((K_{1,n-2}+e)\vee K_1)>H_f(C_{n-1}\vee K_1)\]

since this is equivalent to 2f(n − 1) + 2f(3) + (n − 4)f(2) > f(n − 1) + (n − 1)f(3) or f(n − 1) − (n − 3)f(3) + (n − 4)f(2) > 0. This inequality holds by Lemma 2.2. It follows that G is not extremal, a contradiction.

Case 2. If δ(G) = 2 there exists a vertex u ∈ V (G) such that d(u) = 2. Suppose that N(u) = {v, t}. We get d(t) ≤ n − 1 and G − u is a quasi-unicyclic graph of order n − 1. By the induction hypothesis we obtain:

\[H_f(G) = H_f(G - u) + f(d(t)) - f(d(t) - 1) + f(2) + f(n - 1) - f(n - 2)\] \[\leq 2f(n - 2) + 2f(3) + (n - 5)f(2) + f(d(t)) - f(d(t) - 1) + f(2) + f(n - 1) - f(n - 2)\] \[\leq 2f(n - 1) + 2f(3) + (n - 4)f(2)\]

if and only if f(d(t))−f(d(t)−1) ≤ f(n−1)−f(n−2).This inequality holds since the function f(x) − f(x − 1) is strictly increasing for x ≥ 2. Equality holds only for d(t) = n − 1 and G − u = (K1,n−³ + e) ∨ K1. In this case we get G = (K1,n−² + e) ∨ K1. The proof was done. When f(x) is strictly concave and strictly decreasing the proof is analogous.

In what follows we shall deduce results similar to theorems 3.1-3.4 for quasi-unicyclic graphs of given order and a fixed number of pendant vertices.

Theorem 3.5. Let G be a quasi-unicyclic graph of order n with p pendant vertices, where \(n \ge 4\), \(1 \le p \le n-3\) and f(x) be strictly concave and strictly increasing (strictly convex and strictly decreasing, respectively). Then minimum (maximum, respectively) of \(H_f(G)\) equals

\[f(p+2) + (n-p-1)f(2) + pf(1)\].

There are several extremal graphs, each consisting of one cycle \(C_k\), where \(3 \le k \le n - p\) and p paths attached to a unique vertex of this cycle.

Proof. Since f(x) is strictly increasing it follows that the minimum of \(H_f(G)\) occurs when for a quasi-vertex v we have d(v) = 1. In this case G is a unicyclic graph and one applies Lemma 2.4. The proof follows on the same way when f(x) is strictly convex and strictly decreasing, respectively.

Theorem 3.6. Suppose that G is a quasi-unicyclic graph of order n with p pendant vertices, where \(n \geq 4\), \(1 \leq p \leq n-3\) and f(x) is strictly convex and strictly increasing (strictly concave and strictly decreasing, respectively). Then minimum (maximum, respectively) of \(H_f(G)\) equals

\[rf(q+3) + (n-p-r)f(q+2) + pf(1),\]

where \(q = \lfloor \frac{p}{n-p} \rfloor\) and \(r = p - (n-p) \lfloor \frac{p}{n-p} \rfloor\). A graph is extremal if and only if it has degrees \((q+3)^r, (q+2)^{n-p-r}, 1^p\). An example of an extremal graph consists of \(C_{n-p}\) and p pendant edges attached to the vertices of this cycle such that the numbers of pendant edges attached to any two vertices of \(C_{n-p}\) differ by at most one.

Proof. Let G be a quasi-unicyclic graph such that \(H_f(G)\) is minimum and let v be a quasi-vertex. Since f(x) is strictly increasing, we deduce that d(v)=1, thus implying that G is a unicyclic graph of order n having p pendant vertices. In this case the degree sequence of G is \(\mathbf{x}=(d_1,d_2,\ldots,d_{n-p},1,\ldots,1)\in D_{n,2n}\), the last p components are equal to one and \(\sum_{i=1}^{n-p}d_i=2n-p\). We have \(\min H_f(G)=\min F(\mathbf{x})\) if the point \(\mathbf{x}\) of minimum is a graphical sequence. Since f(x) is strictly convex it follows that this minimum is reached if and only if \(d_1-d_{n-p}\leq 1\). We have 2n-p=2(n-p)+p and \(\lfloor \frac{2n-p}{n-p}\rfloor=2+\lfloor \frac{p}{n-p}\rfloor\). Let p=(n-p)q+r, where \(0\leq r\leq n-p-1\). It follows that \(q=\lfloor \frac{p}{n-p}\rfloor\), r vertices have degree q+3 and q-p-r vertices have degree q+2. An extremal graph having this degree sequence may be obtained from \(C_{n-p}\) and p pendant edges attached to the vertices of this cycle such that the numbers of edges attached to vertices of \(C_{n-p}\) compose an equipartition of p. A similar situation occurs for the maximum of \(C_{n-p}\) is strictly concave and strictly decreasing, respectively.

Theorem 3.7. Let G be a quasi-unicyclic graph of order n with p pendant vertices, where \(n \geq 5\), \(1 \leq p \leq n-4\) and f(x) be a strictly concave and strictly increasing (strictly convex and strictly decreasing, respectively) function. Then maximum (minimum, respectively) of \(H_f(G)\) equals

\[f(n-p-1) + rf(q+4) + (n-p-1-r)f(q+3) + pf(1),\]

where \(q = \lfloor \frac{p}{n-p-1} \rfloor\) and \(r = p - (n-p-1) \lfloor \frac{p}{n-p-1} \rfloor\). A graph is extremal if and only if it has degrees \(n-p-1, (q+4)^r, (q+3)^{n-p-r-1}, 1^p\). An example of an extremal graph consists of \(C_{n-p-1} \vee K_1\) and p pendant edges attached to the vertices of \(C_{n-p-1}\) such that the numbers of pendant edges attached to any two vertices of the cycle differ by at most one.

Proof. Let G be a quasi-unicyclic graph of order n with p pendant vertices \(v_1, \ldots, v_p\) such that \(H_f(G)\) is maximum and v be a quasi-vertex. Since G-v is a unicyclic graph, then v cannot be adjacent to any pendant vertex of G and since f(x) is strictly increasing it follows that v is adjacent to all vertices of G which are not pendant. We get d(v) = n - p - 1. Also we obtain |E(G-v)| = n-1, which implies \(\sum_{u \in V(G) \setminus \{v, v_1, \dots, v_p\}} d(u) = 2(n-1) + n - p - 1 - p = 3n - 2p - 3\). In this case the degree sequence of G is \(\mathbf{x} = (d_1, d_2, \dots, d_{n-p}, 1, \dots, 1) \in D_{n,4n-2p-4}\), the last pcomponents are equal to one, one component from \(d_1, d_2, \ldots, d_{n-p}\) is equal to n-p-1 and the sum of the components different from 1 and n-p-1 is equal to 3n-2p-3. We have \(\max H_f(G) = \max F(\mathbf{x})\) if the point \(\mathbf{x}\) of maximum is a graphical sequence. Since f(x) is strictly concave it follows that this maximum is reached if and only if the components different from 1 and n-p-1 differ by at most one. Let 3n-2p-3=(n-p-1)s+r, where and r = 3n - 2p - 3. Since \(\lfloor \frac{3n - 2p - 3}{n - p - 1} \rfloor = \lfloor \frac{p}{n - p - 1} \rfloor + 3\), it follows that s = q + 3, where \(q = \lfloor \frac{p}{n - p - 1} \rfloor\) and \(r = 3n - 2p - 3 - (n - p - 1)(\lfloor \frac{p}{n - p - 1} \rfloor + 3) = p - (n - p - 1)\lfloor \frac{p}{n - p - 1} \rfloor\). We obtain that \(r = 2n - 2p - 3 - (n - p - 1)(\lfloor \frac{p}{n - p - 1} \rfloor + 3) = p - (n - p - 1)(\lfloor \frac{p}{n - p - 1} \rfloor + 3)\). vertices in G, different from v have degree q+4 and n-p-1-r have degree q+3. An extremal graph having this degree sequence may be obtained from the wheel \(C_{n-p-1} \vee K_1\) and p pendant edges attached to the vertices of \(C_{n-p-1}\) such that the numbers of edges attached to vertices of \(C_{n-p-1}\) compose an equipartition of p. A similar situation occurs for the minimum of \(H_f(G)\) if f(x) is strictly convex and strictly decreasing, respectively.

Theorem 3.8. Suppose that G is a quasi-unicyclic graph of order n with p pendant vertices, where \(n \geq 5\), \(1 \leq p \leq n-4\) and f(x) is strictly convex and strictly increasing (strictly concave and strictly decreasing, respectively). Then maximum (minimum, respectively) of \(H_f(G)\) equals

\[f(n-1) + f(n-p-1) + 2f(3) + (n-p-4)f(2) + pf(1).\]

Extremal graph reaching this bound is unique and it is obtained from a vertex v and \(K_{1,n-2} + e\) by joining v with non-pendant vertices and n - p - 4 pendant vertices of \(K_{1,n-2} + e\).

Proof. Let G be a quasi-unicyclic graph of order n with p pendant vertices \(v_1,\ldots,v_p\) such that \(H_f(G)\) is maximum and let v be a quasi-vertex. As before, since G-v is a unicyclic graph, then v cannot be adjacent to any pendant vertex of G and because f(x) is strictly increasing it follows that v is adjacent to all vertices of G which are not pendant, which implies d(v)=n-p-1. We shall prove first that \(v_1,\ldots,v_p\) are adjacent to the same vertex in G. Suppose that there exist two vertices \(u,t\in V(G)\) such that they are adjacent each with some pendant vertices. Let d(u)=r and d(t)=s, respectively and \(r,s\geq 2\) and \(r\leq s\). If we move one pendant edge from u to t we get another quasi-unicyclic graph \(G_1\) of order n with p pendant vertices and

\[H_f(G) - H_f(G_1) = f(r) + f(s) - f(s+1) - f(r-1) < 0\]

by Lemma 2.1, since f(x) is strictly convex, a contradiction.

Let C denote the unique cycle of F = G−v. We will prove that F has a unique pendant tree T attached to a vertex y of C. F has two types of pendant vertices: pendant vertices v1, . . . , v^p of G and some other pendant vertices denoted by z1, . . . , z^s which are adjacent also to the quasi-vertex v in G. By a similar argument as before, we get that all p + s pendant vertices of F are adjacent to a unique vertex w of F. It follows that F consists of a cycle C and a unique pendant tree T attached to a vertex y of C.

We shall show that T is a star with y the central vertex in C.

If T is not a star with y the central vertex, it follows that T consists of a path y, . . . , w and pendant edges wv1, . . . , wvp, wz1, . . . , wz^s since all pendant vertices of F are adjacent to the same vertex in G. Define another quasi-unicyclic graph of order n with p pendant vertices G² = G − {wv1, . . . , wvp, wz1, . . . , wzs} + {yv1, . . . , yvp, yz1, . . . , yzs}. Since all vertices of G which are not pendant are adjacent with v, it follows that

\[H_f(G_2) - H_f(G) = f(p+s+4) + f(2) - f(p+s+2) - f(4) > 0\]

by Lemma 2.1, a contradiction.

It remains to prove that the length of C is equal to three. Suppose that the length of C is k ≥ 4, C = v1, v2, . . . , vk, v¹ and the star has its center in v1. We obtain that in G−v vertex v¹ is adjacent to n − k − 1 pendant vertices. Let G³ = G − v2v³ + v1v3. G³ is a quasi-unicyclic graph of order n with p pendant vertices where n − k − 1 ≥ p ≥ 1 and

\[H_f(G_3) - H_f(G) = f(n-k+3) + f(2) - f(n-k+2) - f(3) > 0\]

by Lemma 2.1, a contradiction. This concludes the proof.

The extremal graph is the same also for the case of minimization when f(x) is strictly concave and strictly decreasing, respectively.

4. Concluding remarks

In this paper we have solved an optimization problem concerning the vertex-degree function index H^f (G) in four classes of functions f(x) for quasi-unicyclic graphs G of given order or of given order and fixed number of pendant vertices. These classes are characterized by: A– strictly convex and strictly increasing functions; B–strictly convex and strictly decreasing functions; C– strictly concave and strictly increasing functions and D–strictly concave and strictly decreasing functions.

All topological indices mentioned above are related to vertex-degree function indices H^f (G):

• 1) ⁰Rα(G) = P v∈V (G) d(v) α , corresponds to f(x) = x α , where x ≥ 1. For α > 1 f ∈ A ; for 0 < α < 1 f ∈ C; for α < 0 f ∈ B.
• 2) The first general multiplicative Zagreb index P α 1 (G) = Q u∈V (G) d(u) α is maximum/minimum if and only if ln P α 1 (G) = α P u∈V (G) ln d(u) is maximum/minimum. In this case f(x) = α ln x, where x ≥ 1. For α > 0 f ∈ C and for α < 0 f ∈ B.
• 3) The second general multiplicative Zagreb index is P α 2 (G) = Q u∈V (G) d(u) αd(u) . We have ln P α 2 (G) = α P u∈V (G) d(u) ln d(u) and f(x) = αx ln x, where x ≥ 1. For α > 0 f ∈ A and for α < 0 f ∈ D.

4) The sum lordeg index \[SL(G) = \sum_{v \in V(G)} d(v) \sqrt{\ln d(v)} = \sum_{v \in V(G): d(v) \geq 2} d(v) \sqrt{\ln d(v)}\]. We get \(f(x) = x \sqrt{\ln x}\), where \(x \geq 2\) and \(f \in A\).

References

• [1] M.R. Alfuraidan, S. Balachandran, and T. Vetr´ık, General multiplicative Zagreb indices of unicyclic graphs, Carpathian J. Math. 37 (2021), 1–11.
• [2] M. Anghel, A. Erfanian, and A.R. Ashrafi, On first and second Zagreb indices of quasi unicyclic graphs, Transactions on Combinatorics, 8, 3(2019), 29–38.
• [3] J. Du and X. Sun, Quasi-tree graphs with extremal general multiplicative Zagreb indices, IEEE Access, 8 (2020), 194676–194684.
• [4] J. Du and X. Sun, Extremal quasi-unicyclic graphs with respect to the general multiplicative Zagreb indices, Discrete Applied Mathematics, 325 (2023), 200–211.
• [5] I. Gutman and N. Trinajstic, Graph theory and molecular orbitals. Total ´ π−electron energy of alternant hydrocarbons, Chem. Phys. Lett., 17 (1972), 535–538.
• [6] X. Li and I. Gutman, Mathematical aspects of Randic-type molecular structure descriptors, ´ Mathematical Chemistry Monographs No. 1, Univ. Kragujevac, 2006.
• [7] X. Li and J. Zheng, A unified approach to the extremal trees for different indices, MATCH Commun. Math. Comput. Chem., 54 (2005), 195–208.
• [8] R. Todeschini and V. Consonni, New local vertex invariants and molecular descriptors based on functions of the vertex degrees, MATCH Commun. Math. Comput. Chem., 64 (2010), 359–372.
• [9] I. Tomescu, Minimizing vertex-degree function index for k-generalized quasi-unicyclic graphs, The Art of Discrete and Applied Mathematics, 5 (2022) #P1.02
• [10] T. Vetr´ık and S. Balachandran, General multiplicative Zagreb indices of trees, Discrete Appl. Math. 247 (2018), 341–351.
• [11] T. Vetr´ık and S. Balachandran, General multiplicative Zagreb indices of trees and unicyclic graphs with given matching number, J. Comb. Optim. 40 (2020), 953–973.
• [12] D. Vukicevi ˇ c and M. Ga ´ sperov, Bond additive modeling 1. Adriatic indices, ˇ Croat. Chem. Acta, 83 (2010), 243–260.
• [13] D.B. West, Introduction to Graph Theory, 2nd Edition, Prentice-Hall, 2001.
• [14] Y. Yao, M. Liu, F. Belardo, and C. Yang, Unified extremal results of topological indices and spectral invariants of graphs, Discrete Appl. Math., 271 (2019), 218–232, doi:10.1016/j.dam.2019.06.005.