Int. J. Anal. Appl. (2022), 20:6

On the Uphill Zagreb Indices of Graphs

Anwar Saleh∗, Sara Bazhear and Najat Muthana

Department of Mathematics, Faculty of Science, University of Jeddah, Jeddah, Saudi Arabia

∗Corresponding author: asaleh1@uj.edu.sa

Abstract. One of the tools, to research and investigation the structural dependence of various prop-

erties and some activities of chemical structures and networks is the topological indices of graphs. In

this research work, we introduce novel indices of graphs which they based on the uphill degree of the

vertices termed as uphill Zagreb topological indices. Exact formulae of these new indices for some

important and famous families of graphs are established.

1. Introduction

In this research, by graphs, we mean undirected finite simple graph. We denote G = (V,E) for a

graph, where V is the set of vertices and E is the set of edges. For a vertex v ∈ V (G) the degree
of v, d(v) is the number of edges incident with v. Any terminology or notation which, we did not

mention its definition, we refer the reader to [3].

Topological indices have a widespread position specifically in pharmacology, chemistry, networks and

many others. (see [8, 9, 13–15, 18, 24, 25]). Almost of the indices of contemporary interesting in

mathematical chemistry are introduced based on vertex degrees of the chemical graph. The two

well-known topological indices of graphs are the Zagreb indices that have been introduced by Gutman

and Trinajstic by their work in [16], and described as M1 (G) =
∑
u∈V (G) (d (u))

2 and M2 (G) =∑
uv∈E(G)d (u) d (v), respectively. The forgotten topological index was introduced by Furtula and

Gutman [10] as F (G) =
∑
u∈V (G) (d (u))

3
.

Zagreb indices were studied considerably due to their numerous applications inside the area of present

chemical methods which want extra time and more charges. Many new reformulated and prolonged

versions of the Zagreb indices have been delivered for several similar reasons (cf. [1,4,12,19,22,27–29]).

Received: Nov. 14, 2021.

2010 Mathematics Subject Classification. 05C35, 05C07, 05C40.

Key words and phrases. first uphill Zegrib index; second uphill Zegrib index; forgotten uphill Zegrib index.

https://doi.org/10.28924/2291-8639-20-2022-6
ISSN: 2291-8639

© 2022 the author(s).

https://doi.org/10.28924/2291-8639-20-2022-6


2 Int. J. Anal. Appl. (2022), 20:6

The uphill domination and some related concepts are introduced and studied in ( [7,23]). In this paper

motivated by the large applications of topological indices and the concept of uphill domination, we

introduce novel indices of graphs based on a new degree (uphill degree) of the vertices termed as uphill

Zagreb topological indices. Some properties and exact formulae of these new topological indices for

some standard and famous families of graphs are established.

2. Some Results on the Uphill Zagreb Indices of Graphs

Definition 2.1. [7] For any graph G = (V,E). A path u −v is a sequence of vertices in G, initialing
with u and terminal at v, such that sequential vertices are adjacent, and no vertex is repeated. A path

P = v1,v2, ...vk+1 in G is an uphill path if for every i,1 ≤ i ≤ k, deg(vi ) ≤ deg(vi+1).
For any vertices u and v in G, if there is an uphill path from u to v we say that u is uphill adjacent

to v.

Definition 2.2. A vertex v is uphill dominates a vertex u in a graph G if v uphill adjacent to u.

An uphill neighborhood of the vertex v is denoted by Nup(v) and described as: Nup(v) = {u :
v uphill adjacent to u }. The uphill degree of the vertex v, denoted by dup(v), is the number of
vertices which v uphill adjacent them, that means dup(v) = |Nup(v)|.
The uphill closed neighborhood, Nup[v], of the vertex v is the uphill open neighborhood of v together

with the vertex v.

The maximum and minimum uphill degrees in the graph G denoted by ∆up(G) and δup(G), respectively.

The vertex with uphill degree equal to zero is called uphill isolated vertex.

In this paper by Ex,y, we mean that Ex,y = {uv ∈ E(G) : dup(u) = x and dup(v) = y}.

Definition 2.3. For any graph G = (V,E) the first uphill Zagreb, second uphill Zagreb, forgotten

uphill Zagreb index and modified first uphill Zagreb are defined as:

UPM1(G) =
∑

v∈V (G)

(dup(v))
2,

UPM2(G) =
∑

vu∈E(G)

dup(v)dup(u),

UPM∗1(G) =
∑

vu∈E(G)

(dup(v) + dup(u)),

and

UPF (G) =
∑

v∈V (G)

(dup(v))
3.

Lemma 2.1. Suppose G be a graph, for any two vertices u and v, where u is uphill adjacent to v, if

d(u) < d(v). Then dup(u) > dup(v).



Int. J. Anal. Appl. (2022), 20:6 3

Proof. If G is a graph, where u and v be any two vertices in G, where u is uphill adjacent to v. Then

there are two cases:

Case 1. When u is adjacent with v. Without loss of generality, suppose that Nup(v) = {v1,v2, ...,vr},
where r = dup(v). In this case,

Nup[v] ⊆ Nup(u).

Hence,

dup(u) > dup(v).

Case 2. When u not adjacent with v. Then, there is an uphill path Γ from u to v. Clearly,

dup(u) ≥ dup(v) + k + 1, where k is the number of internal vertices in Γ.
Hence,

dup(u) > dup(v).

�

Definition 2.4. A graph G is called k-uphill regular graph if ∆up(G) = δup(G) = k.

Theorem 2.1. Let G be any graph. Then, the graph G is regular if and only if G is uphill regular.

Proof. If G is regular graph of n vertices. Then it is straightforward, that G is n − 1 uphill regular
graph.

To prove the other direction of the theorem, we will prove that if G is not regular then G is not uphill

regular. Suppose that G is not regular. Then, there exist at least two vertices say u and v such that

d(u) < d(v). We have two cases:

Case 1. If u is uphill adjacent to v. Then, By Lemma 2.1, the graph G is not uphill regular.

Case 2. If u is not uphill adjacent to v. Then, there exist at least two adjacent vertices in some paths

from u to v say w and w1, where d(w) > d(w1). By Lemma 2.1, we get dup(w1) > dup(w). Hence,

the graph G is not uphill regular. �

Proposition 2.1. For any graph G, UPM2(G) = 0 if and only if for each edge e = uv, either u or v

is uphill isolated vertex.

Proposition 2.2. For any graph G,
∑
v∈V (G)dup(v) ≤ τ(G), where τ(G) is the number of uphill paths

in G. Furthermore, the equality holds for the graph without cycle (acylic).

Proof. Let G be any graph and let τ(G) be the number of uphill paths in G, for any vertex v in G

it is obviously from the definition of uphill degree of the vertex that, dup(v) is less than or equal the



4 Int. J. Anal. Appl. (2022), 20:6

number of paths in G which originated from v. Also if we denote by Γv as the number of uphill paths

in G originated from v, then τ(G) =
∑
v∈V (G) Γv. Therefore,∑

v∈V (G)

dup(v) ≤
∑

v∈V (G)

Γv = τ(G).

Furthermore, it is easy to check that if G is acyclic, then dup(v) = Γv. Hence the equality holds. �

Proposition 2.3. Let G ∼= Pn, be a path of n ≥ 3 vertices. Then,

i. UPM1(G) = n3 − 6n2 + 13n− 10,
ii. UPM2(G) = n3 − 7n2 + 17n− 15,
iii. UPM∗1(G) = 2n

2 − 8n + 8,
iv. UPF (G) = n4 − 9n3 + 33n2 − 57n + 38.

Proof. Suppose G ∼= Pn be a path of n ≥ 3 vertices. Then there are two vertices with uphill degree
n− 2 and n− 2 vertices of uphill degree n− 3. So by using the definition of first uphill index we get,

UPM1(G) = 2(n− 2)2 + (n− 2)(n− 3)2

= n3 − 6n2 + 13n− 10.

Similarly,

UPF (G) = 2(n− 2)3 + (n− 2)(n− 3)3

= n4 − 9n3 + 33n2 − 57n + 38.

There are two edges of the type En−2,n−3 and n− 3 edges of the type En−3,n−3. Then,

UPM2(G) = 2[(n− 2)(n− 3)] + (n− 3)3

= n3 − 7n2 + 17n− 15.

In the same way we get

UPM∗1(G) = 2(2n− 5) + (n− 3)(2n− 6)

= 2n2 − 8n + 8.

�

Proposition 2.4. Let G = (V,E) be a regular graph of degree k and has n vertices. Then,

i. UPM1(G) = n(n− 1)2,
ii. UPM2(G) =

nk(n−1)2
2

,

iii. UPM∗1(G) = nk(n− 1),
iv. UPF (G) = n(n− 1)3.

Proof. Let G = (V,E) be k− regular graph with n vertices. Then it isn’t difficult to see that between
any two vertices of G there exists an uphill path, so for any v ∈ V (G), we have dup(v) = n−1. Hence,
UPM1(G) = n(n−1)2, UPM2(G) =

nk(n−1)2
2

, UPM∗1(G) = nk(n−1) and UPF (G) = n(n−1)
3. �



Int. J. Anal. Appl. (2022), 20:6 5

Corollary 2.1. For any complete graph Kn, we have

i. UPM1(Kn) = UPM∗1(G) = n(n− 1)
2,

ii. UPM2(Kn) =
n(n−1)3
2

,

iii. UPF (Kn) = n(n− 1)3.

Corollary 2.2. For any cycle Cn, where n ≥ 3,

i. UPM1(Cn) = UPM2(Cn) = n(n− 1)2,
ii. UPM∗1(Cn) = 2n(n− 1),
iii. UPF (Cn) = n(n− 1)3.

By a graph Wn, we mean a wheel graph of n + 1 vertices.

Proposition 2.5. Let G ∼= Wn, where n ≥ 3 be a wheel graph. Then,

i. UPM1(G) = UPM2(G) = n3,

ii. UPM∗1(G) = 2n
2,

iii. UPF (G) = n4.

Proof. Let G ∼= Wn, where n ≥ 3 be a wheel graph. The graph G has one vertex of uphill degree zero
and n vertices of uphill degree n. Then,

UPM1(G) = n(n)
2 + 0

= n3.

In the same way, we get the forgotten uphill index

UPF (G) = n(n)3 + 0

= n4.

There are n edges of the type En,n and n edges of the type En,0. Then,

UPM∗1(G) = 2n
2

and

UPM2(G) = n(n)
2

= n3.

�

A tadpole graph Tm,n is constructed by joining between Cm and Pn by a bridge [17].

Proposition 2.6. Let G ∼= Tm,n, where m,n ≥ 3 be a tadpole graph of m + n vertices. Then,

i. UPM1(G) = m3 − 3m2 + 3m− 2 + n3 − 2n2 + 3n,
ii. UPM2(G) = m3 − 4m2 + 5m− 4 + n3 − 3n2 + 4n,



6 Int. J. Anal. Appl. (2022), 20:6

iii. UPM∗1(G) = 2m
2 − 4m + 2n2 − 5n + 5,

iv. UPF (G) = m4 − 4m3 + 6m2 − 4m + 2 + n4 − 3n3 + 6n2 − 4n.

Proof. Let G ∼= Tm,n, where m,n ≥ 3 be a tadpole graph of m + n vertices. There are m− 1 vertices
of uphill degree m− 1, one vertex of uphill degree zero, n− 1 vertices of uphill degree n− 1 and one
vertex of uphill degree n. Then, we get

UPM1(G) = (m− 1)3 + (n− 1)3 + (n)2

= m3 − 3m2 + 3m− 2 + n3 − 2n2 + 3n.

Similarly,

UPF (G) = (m− 1)4 + (n− 1)4 + (n)3

= m4 − 4m3 + 6m2 − 4m + 2 + n4 − 3n3 + 6n2 − 4n.

Type Number of edges

Em−1,0 2

Em−1,m−1 m− 2

E0,n−1 1

En−1,n−1 n− 2

En−1,n 1

Table 1. Edge partition of tadpole graph based on uphill degree of end vertices.

Now, by using the partition given in Table1, we get

UPM2(G) = (m− 1)2(m− 2) + (n− 1)2(n− 2) + n(n− 1)

= m3 − 4m2 + 5m− 4 + n3 − 3n2 + 4n.

Also,

UPM∗1(G) = 2 (m− 1) + (m− 2) (2m− 2) + (n− 1) + (2n− 2) (n− 2)

= 2m2 − 4m + 2n2 − 5n + 5.

�

The graph which obtained from a wheel graph with extra vertex between each pair of adjacent

vertices of the outer cycle is called gear graph Gn [17].

Proposition 2.7. Let G ∼= Gn, where n ≥ 4 be a gear graph. Then,

i. UPM1(G) = 10n,



Int. J. Anal. Appl. (2022), 20:6 7

ii. UPM2(G) = 6n,

iii. UPM∗1(G) = 9n,

iv. UPF (G) = 28n.

Proof. Let G ∼= Gn, where n ≥ 4 be a gear graph. Then, there are n vertices of uphill degree one,
one vertex of uphill degree zero and n vertices of uphill degree three. Clearly, we get

UPM1(G) = n + 9n

= 10n.

In the same way, we get

UPF (G) = n + 27n

= 28n.

There are n edges of the type E1,0 and 2n edges of the type E1,3. Then,

UPM∗1(G) = 9n,

UPM2(G) = 6n.

�

The windmill graph Wd(s,k), where s,k ≥ 2, is a graph of k copies of complete graph Ks at a
shared common vertex [17].

Proposition 2.8. Let G ∼= Wd(s,k), where s ≥ 3 and k ≥ 2 be a windmill graph of k(s − 1) + 1
vertices. Then,

i. UPM1(G) = k(s − 1)3,
ii. UPM2(G) = k(s − 1)3(s−22 ),
iii. UPM∗1(G) = k (s − 1)

3
,

iv. UPF (G) = k(s − 1)4.

Proof. Let G ∼= Wd(s,k), where s ≥ 3 and k ≥ 2 be a windmill graph of k(s − 1) + 1 vertices. The
graph G has one vertex of uphill degree zero and k(s − 1) vertices of uphill degree s − 1. So,

UPM1(G) = k(s − 1)(s − 1)2

= k(s − 1)3.

Similarly,

UPF (G) = k(s − 1)(s − 1)3

= k(s − 1)4.

There are sk(s−1)
2
−k(s−1) edges of the type Es−1,s−1 and k(s−1) edges of the type Es−1,0 . Then,

UPM2(G) = (s − 1)2[
sk(s − 1)

2
−k(s − 1)]



8 Int. J. Anal. Appl. (2022), 20:6

= k(s − 1)3[
s − 2

2
].

Also,

UPM∗1(G) =
k (s − 1) (s − 2)

2
(2s − 2) + k (s − 1) (s − 1)

= (s − 1) (k (s − 1) (s − 2) + k (s − 1))

= k (s − 1)3 .

�

The graph which is obtained from Wn by adding an end edge to each outer vertex of Wn, is called

helm graph and denoted by Hn [17].

Proposition 2.9. Let G ∼= Hn, where n ≥ 3 be a helm graph of 2n + 1 vertices. Then,

i. UPM1(G) = 2n3 + 2n2 + n,

ii. UPM2(G) = 2n3 + n2,

iii. UPM∗2(G) = 5n
2 + n,

iv. UPF (G) = 2n4 + 3n3 + 3n2 + n.

Proof. Let G ∼= Hn, where n ≥ 3 be a helm graph. The graph G has only one vertex of uphill degree
zero, n vertices of uphill degree n + 1 and n vertices of uphill degree n. Then,

UPM1(G) = n(n + 1)
2 + n(n)2

= 2n3 + 2n2 + n.

Similarly,

UPF (G) = n(n + 1)3 + n(n)3

= 2n4 + 3n3 + 3n2 + n.

There are n edges of the type En+1,n, n edges of the type En,n and n edges of the type En,0. Then,

UPM2(G) = n
2(n + 1) + n3

= 2n3 + n2.

Similarly,

UPM∗1(G) = n(2n + 1) + 2n(n) + n
2

= 5n2 + n.

�

The double star graph Sr,t which obtained from complete graph of two vertices by joining r pendent

edges to one vertex and t pendent edges to the other vertex of the complete graph K2 [17].

Theorem 2.2. Let G ∼= Sr,t, where r,t ≥ 2 be a double star graph. Then,



Int. J. Anal. Appl. (2022), 20:6 9

i. UPM1(G) =


8r + 2 if r = t;

4r + t + 1 if r < t.

ii. UPM2(G) =


4r + 1 if r = t;

2r if r < t.

iii. UPM∗1(G) =


6r + 2 if r = t;

3r + t + 1 if r < t.

iv. UPF (G) =


16r + 2 if r = t;

8r + t + 1 if r < t.

Proof. Let G ∼= Sr,t, where r,t ≥ 2 be a double star with r + t + 2 vertices. Then,

i. There are two cases:

Case 1. If r = t, it has two vertices of uphill degree one and there are 2r vertices of uphill degree

2, then UPM1(G) = 8r + 2.

Case 2. If r < t, there are r vertices of uphill degree 2 and s + 1 vertices of uphill degree one,

also one uphill isolated vertex, then UPM1(G) = 4r + t + 1.

ii. We have two cases:

Case 1. If r = t, it has one edge of the type E1,1 and there are 2r edges in G, where each edge

of the type E1,2,then UPM2(G) = 4r + 1.

Case 2. When r < t, there are t + 1 edges where each edge of the type E1,0. Also, there are r

edges where each edge of the type E2,1,then UPM2(G) = 2r.

iii. Similarly as in part ii, if r = t, then UPM∗1(G) = 6r + 2. If r < t, then UPM
∗
1(G) = 3r + t + 1.

iv. The proof is similarly to part i.

�

The subdivision graph S(G) of the graph G is a graph obtained from G by replacing each of its

edge by a path of length 2. By simple calculation, we get the uphill Zagreb indices for the subdivision

graphs of path, cycle and complete graph.

Proposition 2.10. Let G ∼= S(Pn), where n ≥ 3. Then,

i. UPM1(G) = 8n3 − 36n2 + 56n− 30,
ii. UPM2(G) = 8n3 − 40n2 + 68n− 40,
iii. UPM∗1(G) = 8n

2 − 24n + 18,
iv. UPF (G) = 16n4 − 104n3 + 264n2 − 308n + 138.

Proposition 2.11. Let G ∼= S(Cn), where n ≥ 3. Then,

i. UPM1(G) = UPM2(G) = 2n(2n− 1)2,
ii. UPM∗1(G) = 2n(4n− 2),



10 Int. J. Anal. Appl. (2022), 20:6

iii. UPF (G) = 2n(2n− 1)3.

Proposition 2.12. Let G ∼= S(Kn), where n ≥ 4. Then,

i. UPM1(G) = 2n(n− 1),
ii. UPM2(G) = 0,

iii. UPM∗1(G) = 2n(n− 1),
iv. UPF (G) = 4n(n− 1).

For each p ≥ 0, the p-sun tree, denoted by Sup, is the tree of order n = 2p + 1 formed by taking
the star on p + 1 vertices and subdividing each edge. For p,q ≥ 0, the (p,q)-double sun, denoted by
DSup,q, is the tree of order n = 2(p + q + 1) obtained by connecting the centers of DSup and DSuq

with an edge [11].

Proposition 2.13. Let G ∼= Sup, where p ≥ 3 be a sun graph of 2p + 1 vertices. Then,

i. UPM1(G) = 5p,

ii. UPM2(G) = 2p,

iii. UPM∗1(G) = 4p,

iv. UPF (G) = 9p.

Proposition 2.14. Let G ∼= Sup,q, where p,q ≥ 2 be a double sun graph of 2(p + q + 1) vertices.
Then,

i. UPM1(G) =


26p + 2 if p = q;

13p + 5q + 1 if p < q.

ii. UPM2(G) =


16p + 1 if p = q;

8p + 3q + 1 if p < q.

iii. UPM∗1(G) =


16p + 2 if p = q;

8p + 3q + 1 if p < q.

iv. UPF (G) =


70p + 2 if p = q;

35p + 9q + 1 if p < q.

The central graph of a graph G is obtained by subdividing each edge of G exactly once and joining

all the non-adjacent vertices of G and denoted by C(G) [2].

Proposition 2.15. Let G ∼= C(Pn), where n ≥ 4 be a central graph of a path with 2n − 1 vertices.
Then,

i. UPM1(G) = n(n− 1)(2n− 1),



Int. J. Anal. Appl. (2022), 20:6 11

ii. UPM2(G) =
n4−n3+n2−3n+2

2
,

iii. UPM∗1(G) = n
3 −n,

iv. UPF (G) = n(n− 1)((n− 1)2 + n2).

Proof. From the definition of the central graph of a graph obviously in C(Pn) there are n vertices of

uphill degree n− 1 and n− 1 vertices of uphill degree n. So,

UPM1(G) = n(n− 1)(2n− 1).

Then clearly,

UPF (G) = n(n− 1)((n− 1)2 + n2).

Type Number of edges

En−1,n 2(n− 1)

En−1,n−1
2(n−2)+(n−2)(n−3)

2

Table 2. Edge partition of C(Pn) graph based on uphill degree of end vertices.

Now, by using the partition in Table 2, we get

UPM2(G) = 2n (n− 1)2 +
(n− 1)3 (n− 2)

2

=
n4 −n3 + n2 − 3n + 2

2
.

By using the same partition in Table 2, we get

UPM∗1(G) = 2 (2n− 1) (n− 1) + (2n− 2)
2 (n− 2) + (n− 2) (n− 3)

2

= n3 −n.

�

Proposition 2.16. Let G ∼= C(Cn), where n ≥ 5 be a central graph of a cycle with 2n vertices. Then,

i. UPM1(G) = n(n− 1)2 + n3,
ii. UPM2(G) = 2n2(n− 1) +

n(n−3)(n−1)2
2

,

iii. UPM∗1(G) = n
3 + n,

iv. UPF (G) = n(n− 1)3 + n4.

Proposition 2.17. For any graph G ∼= C(Kn),

i. UPM1(G) = UPM∗1(G) =
UPF(G)
2

,



12 Int. J. Anal. Appl. (2022), 20:6

ii. UPM2(G) = 0.

Proof. Clearly, there are n(n−1)
2

vertices of uphill degree 2 and all other vertices of uphill degree zero.

Also there are n(n− 1) edges of type E2,0. Then we have

UPM1 = 2n(n− 1),

UPF (G) = 4n(n− 1),

UPM∗1(G) = 2n(n− 1),

UPM2(G) = 0.

�

An (r,s) banana tree denoted by Br,s, is a graph obtained by connecting one leaf of each of r

copies of an star graph of s vertices with a single root vertex that is distinct from all the stars [6].

Theorem 2.3. Let G ∼= Br,s, where s ≥ 4 be a banana tree graph with rs + 1 vertices. Then,

i. UPM1(G) =


2s + 44 if r = 2;
r(s + 2) if r ≥ 3.

ii. UPM2(G) =


32 if r = 2;

0 if r ≥ 3.

iii. UPM∗1(G) =


rs − 2r + 24 if r = 2;
rs + 2r if r ≥ 3.

iv. UPF (G) =


2s + 188 if r = 2;

8r + s − 2 if r ≥ 3.

Proof. Let G ∼= Br,s, where s ≥ 4 be a banana tree graph with rs + 1 vertices. Then,

i. We have two cases:

Case 1. If r = 2, the graph G has two vertices of uphill degree zero, three vertices of uphill degree

four and 2(s − 2) vertices of uphill degree one, then UPM1(G) = 2s + 44.
Case 2. If r ≥ 3, there are r + 1 vertices of uphill degree zero, r vertices of uphill degree two and
r(s − 2) vertices of uphill degree one, then UPM1(G) = r(s + 2).

ii. We have two cases:

Case 1. If r = 2, it has two edges of the type E4,4, two edges of the type E0,4 and there are

r(s − 2) edges in G, where each edge of the type E1,0, then UPM2(G) = 32.
Case 2. If r ≥ 3, there are 2r edges where each edge of the type E0,2. Also, there are r(s − 2)
edges where each edge of the type E1,0, then UPM2(G) = 0.

iii. As part ii, we get UPM∗1(G) = rs + 2r if r ≥ 3 and if r = 2, UPM
∗
1(G) = rs − 2r + 24 .

iv. In the same way as part i.



Int. J. Anal. Appl. (2022), 20:6 13

�

A firecracker graph Fr,s is a graph obtained by the concatenation of n stars, each consists of s

vertices, by linking one leaf from each star [6].

Theorem 2.4. Let G ∼= Fr,s , where s ≥ 5 be a firecracker graph with rs vertices. Then,

i. UPM1(G) =


2S + 14 if r = 2;

2(2r − 3)2 + (r − 2)(2r − 5)2 + r(s − 2) if r ≥ 3.

ii. UPM2(G) =


9 if r = 2;

2(2r − 3)(2r − 5) + (r − 3)(2r − 5)2 if r ≥ 3.

iii. UPM∗1(G) =


2S + 8 if r = 2;

6r2 + rs − 21r + 18 if r ≥ 3.

iv. UPF (G) =


50 + 2s if r = 2;

2(2r − 3)3 + (r − 2)(2r − 5)3 + r(s − 2) if r ≥ 3.

Proof. Let G ∼= Fr,s , where s ≥ 5 be a firecracker graph with rs vertices. Then,

i. There are two cases:

Case 1. If r = 2, the graph G has two vertices of uphill degree zero, two vertices of uphill degree

three and 2(s − 2) vertices of uphill degree one, then UPM1(G) = 2s + 14.
Case 2. If r ≥ 3, there are two vertices of uphill degree 2r − 3, r − 2 vertices of uphill degree
2r−5,r vertices of uphill degree zero and r(s−2) vertices of uphill degree one, then UPM1(G) =
2(2r − 3)2 + (r − 2)(2r − 5)2 + r(s − 2).

ii. There are two cases:

Case 1. If r = 2, the graph G has 2(s − 2) edges of type E1,0, two edges of the type E0,3 and
one edge of type E3,3. So, UPM2(G) = 9.

Case 2. If r ≥ 3, in this case, there are r(s−2) of type E1,0, r −2 edges of the type E0,2r−5, two
edges of the type E0,2r−3, two edges of the type E2r−3,2r−5 and r − 3 edges of type E2r−5,2r−5,
then UPM2(G) = 2(2r − 3)(2r − 5) + (r − 3)(2r − 5)2.

iii. As the method in ii.

iv. As the method in i.

�

Book graph is a Cartesian product of a star and single edge, denoted by Br. The r-book graph is

defined as the graph Cartesian product Sr+1 × P2 , where Sr+1 is a star graph and P2 is the path
graph. The stacked book graph of order (r,t) is defined as the graph Cartesian product Sr+1 ×Pt,
where Sr is a star graph and Pt is the path graph on t nodes, and it is denoted by Br,t [17].

Proposition 2.18. Let G ∼= Br , where r ≥ 2 be a book graph of 2(r + 1) vertices. Then,



14 Int. J. Anal. Appl. (2022), 20:6

i. UPM1(G) = 2(9r + 1),

ii. UPM2(G) = 15r + 1,

iii. UPM∗1(G) = 14r + 2,

iv. UPF (G) = 2(27r + 1).

Proof. Let G ∼= Br , where r ≥ 2 be a book graph of 2(r + 1) vertices. There are two vertices of
uphill degree one and 2r vertices of uphill degree three. Then,

UPM1(G) = 2(9r + 1),

In the same way,

UPF (G) = 2(27r + 1).

The graph G has three kinds of edges, one edge of the type E1,1 , 2r edges of the type E3,1 and r

edges of the type E3,3. Then,

UPM2(G) = 15r + 1.

Also,

UPM∗1(G) = 14r + 2.

�

Theorem 2.5. Let G ∼= Br,t , where r ≥ 2 and t ≥ 3 be a stacked book graph with t(r + 1) vertices.
Then,

i. UPM1(G) = 2r(2t − 3)2 + (t − 2)[(t − 3)2 + 2(t − 2) + r(2t − 5)2],
ii. UPM2(G) = 2r(2t − 3)(3t − 7) + (t − 3)[2(t − 2) + (t − 3)2 + r(2t − 5)2 + r(t − 2)(2t − 5)],
iii. UPM∗1(G) = −22rt + 20r + 2t

2 − 8t + 7rt2 + 8,
iv. UPF (G) = 2r(2t − 3)3 + (t − 2)[(t − 3)3 + 2(t − 2) + r(2t − 5)3].

Proof. Let G ∼= Br,t , where r ≥ 2 and t ≥ 3, be a stacked book graph with
t(r + 1) vertices. In Figure 1, we can see the graph G has 2r vertices are labeled by

(v1,1,v2,1, ...,vr,1) and (v1,t,v2,t, ...,vr,t) of uphill degree 2t − 3, r(t − 2) vertices are labeled by
(v1,2,v1,3, ...,v1,t−1), (v2,2,v2,3, ...,v2,t−1), ..., (vr,2,vr,3, ...,vr,t−1) of uphill degree 2t−5, two vertices
are labeled by (v0,1) and (v0,t) of uphill degree t−2, t−2 vertices are labeled by (v0,2,v0,3, ...,v0,t−1)
of uphill degree t − 3. Then,

UPM1(G) = 2r(2t − 3)2 + (t − 2)[(t − 3)2 + 2(t − 2) + r(2t − 5)2].

Similarly,

UPF (G) = 2r(2t − 3)3 + (t − 2)[(t − 3)3 + 2(t − 2) + r(2t − 5)3].

There are 6 types of edges.



Int. J. Anal. Appl. (2022), 20:6 15

Type Number of edges

E2t−3,2t−5 2r

E2t−3,t−2 2r

Et−2,t−3 2

Et−3,t−3 t − 3

E2t−5,2t−5 r(t − 3)

Et−3,2t−5 r(t − 2)

Table 3. Edge partition of Br,t graph based on uphill degree of end vertices.

In Figure 1, the types of edges, E2t−3,2t−5,E2t−3,t−2,Et−2,t−3, Et−3,t−3,E2t−5,2t−5 and Et−3,2t−5

are colored by green, purple, red, yellow, blue and black, respectively.

Figure 1. Stacked book graph Br,t

Now, by using the partition in Table 3, we get

UPM2(G) = 2r(2t − 3)(3t − 7) + (t − 3)[2(t − 2) + (t − 3)2 + r(2t − 5)2 + r(t − 2)(2t − 5)].

Also,

UPM∗1(G) = −22rt + 20r + 2t
2 − 8t + 7rt2 + 8.



16 Int. J. Anal. Appl. (2022), 20:6

�

A firefly graph Fa,b,c is a graph of n = 2a + 2b + c + 1 vertices that consists of c pendant edges,

a triangles, and b pendant paths of length 2, all of them sharing a common vertex [5].

Proposition 2.19. Let G ∼= Fa,b,c be the firefly graph with 2a + 2b + c + 1 vertices. Then,

i. UPM1(G) = 8a + 5b + c,

ii. UPM2(G) = 2(2a + b),

iii. UPM∗1(G) = 8a + 4b + c,

iv. UPF (G) = 16a + 9b + c.

Proof. Let G ∼= Fa,b,c be the firefly graph with 2a + 2b + c + 1 vertices. In Figure 2, we can see the
graph G has one uphill isolated vertex, 2a vertices are labeled by (v1,v2, ...,v2a) of uphill degree two,

b vertices are labeled by (u1,u2, ...ub) of uphill degree one, b vertices are labeled by (u′1,u
′
2, ...,u

′
b) of

uphill degree two and c vertices are labeled by (w1,w2, ...wc) of uphill degree one. Then,

UPM1(G) = 8a + 5b + c.

Similarly,

UPF (G) = 16a + 9b + c.

There are 4 types of edges.

Type Number of edges

E2,2 a

E2,0 2a

E1,0 b + c

E2,1 b

Table 4. Edge partition of Fa,b,c graph based on uphill degree of end vertices.

In Figure 2, the types of edges, E2,2,E2,0,E1,0 and E2,1 are colored by blue, red, black blue and

green, respectively.



Int. J. Anal. Appl. (2022), 20:6 17

Figure 2. Firefly graph Fa,b,c

Now, by using the edge partition in Table 4, we get

UPM2(G) = 2(2a + b),

and

UPM∗1(G) = 8a + 4b + c.

�

Corollary 2.3. Let G ∼= BF, be the butterfly graph with 2a + c + 1 vertices. Then,

i. UPM1(G) = UPM∗1(G) = 8a + c,

ii. UPM2(G) = 4a,

iii. UPF (G) = 16a + c.

Conflicts of Interest: The author(s) declare that there are no conflicts of interest regarding the

publication of this paper.

References

[1] A. Alwardi, A. Alqesmah, R. Rangarajan, I.N. Cangul, Entire Zagreb indices of graphs, Discrete Math. Algorithm.

Appl. 10 (2018), 1850037. https://doi.org/10.1142/S1793830918500374.

[2] J.A. Aruldoss and G. Gurulakshmi, The dominator coloring of central and middle graph of some special graphs, Int.

J. Math. Appl. 4 (2016), 67–73.

[3] J. A. Bondy and U. S. R. Murty, Graph Theory, Springer, Berlin, 2008.

[4] J. Braun, A. Kerber, M. Meringer, C. Rucker, Similarity of molecular descriptors: the equivalence of Zagreb indices

and walk counts, MATCH Commun. Math. Comput. Chem. 54 (2005), 163-176.

[5] A.E. Brondani, C.S. Oliveira, F.A.M. França, L. de Lima, Aα-spectrum of a firefly graph, Electron. Notes Theor.

Computer Sci. 346 (2019), 209–219. https://doi.org/10.1016/j.entcs.2019.08.019.

https://doi.org/10.1142/S1793830918500374
https://doi.org/10.1016/j.entcs.2019.08.019


18 Int. J. Anal. Appl. (2022), 20:6

[6] W.C. Chen, H.I. Lu, Y.N. Yeh, Operations of interlaced trees and graceful trees, Southeast Asian Bull. Math. 21

(1997), 337-348.

[7] J. Deering, Uphill and downhill domination in graphs and related graph parameters, Thesis, East Tennessee State

University, Johnson, (2013).

[8] M.V. Diudea, Nanomolecules and nanostructures-poynomial and indices, Univ. Kragujevac, 2010.

[9] M.V. Diudea, M.S. Florescu, P.V. Khadikar, Molecular topology and its applications, Eficon, Bucarest, 2006.

[10] B. Furtula, I. Gutman, A forgotten topological index, J Math Chem. 53 (2015), 1184–1190. https://doi.org/

10.1007/s10910-015-0480-z.

[11] W. Gao, The Randić energy of generalized double sun, Czech. Math. J. (2021), 1–28. https://doi.org/10.

21136/CMJ.2021.0463-20.

[12] I. Gutman, K. C. Das, The first Zagreb index 30 years after, MATCH Commun. Math. Comput. Chem. 50 (2004),

83-92.

[13] I. Gutman, B. Furula (Eds.), Novel molecular structure descriptors-theory and applications I, Univ. Kragujevac,

Kragujevac, 2010 .

[14] I. Gutman, B. Furula (Eds.), Novel molecular structure descriptors-theory and applications II, Univ. Kragujevac,

Kragujevac, 2010.

[15] I. Gutman, B. Furula (Eds.), Distance in Molecular Graphs, Univ. Kragujevac, Kragujevac, 2012.

[16] I. Gutman, N. Trinajstić, Graph theory and molecular orbitals. Total φ-electron energy of alternant hydrocarbons,

Chem. Phys. Lett. 17 (1972), 535–538. https://doi.org/10.1016/0009-2614(72)85099-1.

[17] F. Harary, Graph theory, Addison-Wesley, Reading Mass, 1969.

[18] M. Karelson, Molecular descriptors in QSAR-QSPR, Wiley, New York, 2000.

[19] M.H. Khalifeh, H. Yousefi-Azari, A.R. Ashrafi, The first and second Zagreb indices of some graph operations, Discr.

Appl. Math. 157 (2009), 804–811. https://doi.org/10.1016/j.dam.2008.06.015.

[20] J. Kok, N.K. Sudev, U. Mary, On chromatic Zagreb indices of certain graphs, Discrete Math. Algorithm. Appl. 9

(2017), 1750014. https://doi.org/10.1142/S1793830917500148.

[21] S. Nikolić, G. Kovačević, A. Miličević, N. Trinajstić, The Zagreb indices 30 years after, Croat. Chem. Acta, 76

(2003), 113-124.

[22] A. Saleh, A. Aqeel and I. N. Cangul, On the entire ABC index of graphs, Proc. Jangjeon Math. Soc. 23 (2020),

39-51.

[23] A. Saleh, N. Muthana, W. Al-Shammakh, H. Alashwali, Monotone chromatic number of graphs, Int. J. Anal. Appl.

18 (2020), 1108-1122. https://doi.org/10.28924/2291-8639-18-2020-1108.

[24] R. Todeschini, V. Consonni, Handbook of molecular descriptors, Wiley-VCH, Weinheim, 2000.

[25] R. Todeschini, V. Consonni, Molecular descriptors for chemoinformatics, Wiley-VCH, Weinheim, 2009.

[26] S. Wang, B. Wei, Multiplicative Zagreb indices of cacti, Discrete Math. Algorithm. Appl. 8 (2016), 1650040.

https://doi.org/10.1142/S1793830916500403.

[27] B. Zhou, Zagreb indices, MATCH Commun. Math. Comput. Chem. 52 (2004), 113-118.

[28] B. Zhou, I. Gutman, Relations between Wiener, hyper-Wiener and Zagreb indices, Chem. Phys. Lett. 394 (2004),

93–95. https://doi.org/10.1016/j.cplett.2004.06.117.

[29] B. Zhou, I. Gutman, Further properties of Zagreb indices, MATCH Commun. Math. Comput. Chem. 54 (2005),

233-239.

https://doi.org/10.1007/s10910-015-0480-z
https://doi.org/10.1007/s10910-015-0480-z
https://doi.org/10.21136/CMJ.2021.0463-20
https://doi.org/10.21136/CMJ.2021.0463-20
https://doi.org/10.1016/0009-2614(72)85099-1
https://doi.org/10.1016/j.dam.2008.06.015
https://doi.org/10.1142/S1793830917500148
https://doi.org/10.28924/2291-8639-18-2020-1108
https://doi.org/10.1142/S1793830916500403.
https://doi.org/10.1016/j.cplett.2004.06.117

	1. Introduction
	2. Some Results on the Uphill Zagreb Indices of Graphs
	References