Ratio Mathematica Volume 39, 2020, pp. 165-186

KCD indices and coindices of graphs

Keerthi G. Mirajkar*
Akshata Morajkar†

Abstract

The relationship between vertices of a graph is always an interest-
ing fact, but the relations of vertices and edges also seeks attention.
Motivation of the relationship between vertices and edges of a graph
has helped to arise with a set of new degree based topological indices
and coindices named KCD indices and coindices. These indices and
coindices are elaborated by establishing a set of properties. More
fascinating results of some graph operations using KCD indices are
developed in this article.
Keywords: KCD indices, KCD coindices, graph operations.
2010 AMS subject classifications: 05C07, 05C76. 1

*Department of Mathematics, Karnatak University’s Karnatak Arts College, Dharwad - 580
001, Karnataka, INDIA; keerthi.mirajkar@gmail.com

†Department of Mathematics, Karnatak University’s Karnatak Arts College, Dharwad - 580
001, Karnataka, INDIA; akmorajkar@gmail.com

1Received on October 26th, 2020. Accepted on December 17th, 2020. Published on December
31st, 2020. doi: 10.23755/rm.v39i0.550. ISSN: 1592-7415. eISSN: 2282-8214. ©Mirajkar et al.
This paper is published under the CC-BY licence agreement.

165



Keerthi G. Mirajkar and Akshata Morajkar

1 Introduction

Graph theory plays a vital role in the quantification of chemical structures
through topological indices. Topological indices are molecular descriptors which
characterize the topology of a graph through numerical parameters. Abundant
number of topological indices are identified these days. Amongst these the first
degree based topological indices are Zagreb indices [Gutman and Trinajstić, 1972].
Recently along with Zagreb indices Zagreb coindices is also gaining much at-
tention for research. This has put forward versitile forms of Zagreb indices of
graphs. The present work aims to establish some new form of topological indices
of graphs.

This paper considers the graph to be simple, finite and undirected. The
graph is denoted as G = (V, E) with |V (G)| = n as the vertex set and |E(G)| =
m as the edge set. The set of vertices are also referred to as the order of the graph
G and the edge set as the size of the graph G. The edge connecting the two vertices
u and v is denoted as e = uv. The degree of the vertex u in a graph G is denoted as
dG(u) and defined as the number of edges of a graph G incident with the vertex u.
The degree of edge dG(e) of a graph G is defined as dG(e) = dG(u) + dG(v)−2.
The complement G of a graph G is one in which two vertices are adjacent if and
only if they are not adjacent in G. For G, |V (G)| = n, |E(G)| = m =

(
n
2

)
− m

[Alwardi et al., 2018]. Also uv ∈ E(G) ⇐⇒ uv /∈ E(G). The degree of a
vertex u in G is denoted as dG(u) and defined as dG(u) = n − 1 − dG(u) [Al-
wardi et al., 2018]. The degree of edge of G is represented as dG(e), defined as
dG(e) = dG(u) + dG(v)−2. For undefined terminologies refer [Harary, 1969].
The Zagreb indices were defined by Gutman and Trinajstić [Gutman and Trina-
jstić, 1972] as

M1(G) =
∑

u∈V (G)

dG(u)
2 (1)

M2(G) =
∑

uv∈E(G)

dG(u)dG(v) . (2)

Here M1(G) refers first Zagreb index and M2(G) refers second Zagreb index.
First Zagreb index is also expressed as [Došlić, 2008, Došlic et al., 2011]

M1(G) =
∑

uv∈E(G)

(
dG(u) + dG(v)

)
. (3)

For properties and information on Zagreb indices refer [Gutman and Das,
2004, Zhou and Gutman, 2005, Zhou, 2004].

166



KCD indices and coindices of graphs

Further, Zagreb coindices were introduced by Došlić [Došlić, 2008] as

M1(G) =
∑

uv /∈E(G)

(
dG(u) + dG(v)

)
(4)

M2(G) =
∑

uv /∈E(G)

dG(u)dG(v). (5)

The detailed study on Zagreb coindices is reported in [Ashrafi et al., 2010,
2011], the association between Zagreb indices and coindices is encountered in
[Das et al., 2012, Gutman et al., 2015].
Shirdel et al. [Shirdel et al., 2013] defined hyper Zagreb index as

HM(G) =
∑

uv∈E(G)

(
dG(u) + dG(v)

)2
. (6)

Further, hyper Zagreb coindex was introduced as

HM(G) =
∑

uv /∈E(G)

(
dG(u) + dG(v)

)2
. (7)

These graph invariants were studied in [Pattabiraman and Vijayaragavan, 2017,
Veylaki et al., 2016]. Relationship between hyper Zagreb index and coindex is es-
tablished in [Gutman, 2017].

Now, we introduce a set of new degree-based topological indices and coindices
named as Karnatak College Dharwad indices and coindices or KCD indices and
coindices in short, which is dedicated to Karnatak College Dharwad as the college
has completed hundred years of its service in education to the society in the year
2017. Further the research Supervisior and research scholar belong to the same
college.
i.e., The first and second KCD indices of a graph G are respectively

KCD1(G) =
∑

e=uv∈E(G)

((
dG(u) + dG(v)

)
+ dG(e)

)
(8)

KCD2(G) =
∑

e=uv∈E(G)

(
dG(u) + dG(v)

)
dG(e). (9)

We proceed further to define KCD coindices as follows

KCD1(G) =
∑

e=uv /∈E(G)

((
dG(u) + dG(v)

)
+ dG(e)

)
(10)

KCD2(G) =
∑

e=uv /∈E(G)

(
dG(u) + dG(v)

)
dG(e). (11)

167



Keerthi G. Mirajkar and Akshata Morajkar

Here KCD1(G) and KCD2(G) are first and second KCD coindices of a graph
G respectively.

The remaining paper is distributed as follows. Section 2 expresses the prop-
erties of first KCD indices and coindices of a graph and its complement. Section
3 concentrates on properties of second KCD indices and coindices of a graph
and its complement, while Section 4 is devoted for the study of KCD indices of
certain graph operations.
The following previously known results are considered for present investigation.

Theorem 1.1. [Gutman et al., 2015] Let G be a graph with n vertices and m
edges. Then,

M1(G) = M1(G) + n(n−1)2 −4m(n−1) (12)
M1(G) = 2m(n−1)−M1(G). (13)

Corollary 1.2. [Gutman et al., 2015] Let G be any graph and G its complement.
Then

M1(G) = M1(G). (14)

Theorem 1.3. [Gutman, 2017] Let G be a graph with n vertices and m edges.
Then,

HM(G) = 4m2 + (n−2)M1(G)−HM(G) (15)
HM(G) = 2n(n−1)3 −12m(n−1)2 + 4m2 (16)

+(5n−6)M1(G)−HM(G)
HM(G) = 4m(n−1)2 + 4(n−1)M1(G) + HM(G). (17)

2 Basic properties of first KCD indices and coindices
Theorem 2.1. Let G be a graph with n vertices and m edges. Then,

KCD1(G) = (4n−6)m−4m(n−1) + 2M1(G) (18)
KCD1(G) = 4n(m−m)−6m + 4m + 2M1(G) (19)

KCD1(G) = 4m(n−1)−2
(
m + M1(G)

)
(20)

KCD1(G) = (4n−6)m−2M1(G). (21)

Proof.
Proof of Eq. (18):

168



KCD indices and coindices of graphs

For any vertex u of G,

dG(u) = n−1−dG(u). (22)

and for any edge e = uv of G,

dG(e) = 2n−4−
(
dG(u) + dG(v)

)
. (23)

Thus by Eqs. (8), (22) and (23), we have

KCD1(G) =
∑

e=uv∈E(G)

((
dG(u) + dG(v)

)
+ dG(e)

)

=
∑

e=uv /∈E(G)

((
n−1−dG(u) + n−1−dG(v)

)

+
(
2n−4− (dG(u) + dG(v)

))

=
∑

e=uv /∈E(G)

(
4n−6−2

(
dG(u) + dG(v)

))

= (4n−6)m−2
∑

e=uv /∈E(G)

(
dG(u) + dG(v)

)
.

According To Eq. (4)

M1(G) =
∑

uv /∈E(G)

(
dG(u) + dG(v)

)
.

Hence,

KCD1(G) = (4n−6)m−2M1(G) (24)

Substitution of Eqs. (13) and (14) in (24) results into Eq. (18).

Proof of Eq. (19):

For any vertex u of the complement G,

dG(u) = n−1−dG(u). (25)

169



Keerthi G. Mirajkar and Akshata Morajkar

and for any edge e = uv of the complement G,

dG(e) = 2n−4−
(
dG(u) + dG(v)

)
. (26)

Bearing in mind Eqs. (8), (25) and (26), we get

KCD1(G) =
∑

e=uv∈E(G)

((
dG(u) + dG(v)

)
+ dG(e)

)

=
∑

e=uv /∈E(G)

((
n−1−dG(u) + n−1−dG(v)

)

+
(
2n−4− (dG(u) + dG(v)

))

=
∑

e=uv /∈E(G)

(
4n−6−2

(
dG(u) + dG(v)

))

= (4n−6)m−2
∑

e=uv /∈E(G)

(
dG(u) + dG(v)

)
.

Thus by Eq. (4),

KCD1(G) = (4n−6)m−2M1(G) (27)

Employing Eq. (13) in (27) generates Eq. (19).

Proof of Eq. (20):

Using Eqs. (10), (22) and (23), we have

KCD1(G) =
∑

e=uv /∈E(G)

((
dG(u) + dG(v)

)
+ dG(e)

)

=
∑

e=uv∈E(G)

((
n−1−dG(u) + n−1−dG(v)

)

+
(
2n−4− (dG(u) + dG(v)

))

=
∑

e=uv∈E(G)

(
4n−6−2

(
dG(u) + dG(v)

))
.

170



KCD indices and coindices of graphs

By Eq. (3)

M1(G) =
∑

uv∈E(G)

(
dG(u) + dG(v)

)
.

Thus,

KCD1(G) = (4n−6)m−2M1(G) (28)

Substitution of Eq. (12) in (28) gives Eq. (20).

Proof of Eq. (21):

In view of Eq. (10), (25) and (26), we get

KCD1(G) =
∑

e=uv /∈E(G)

((
dG(u) + dG(v)

)
+ dG(e)

)

=
∑

e=uv∈E(G)

((
n−1−dG(u) + n−1−dG(v)

)

+
(
2n−4− (dG(u) + dG(v)

))

=
∑

e=uv∈E(G)

(
4n−6−2

(
dG(u) + dG(v)

))

= (4n−6)m−2
∑

e=uv∈E(G)

(
dG(u) + dG(v)

)

Considering Eq. (3) we directly arrive at Eq. (21).

2

171



Keerthi G. Mirajkar and Akshata Morajkar

3 Basic properties of second KCD indices
and coindices

Theorem 3.1. Let G be a graph with n vertices and m edges. Then,

KCD2(G) = HM(G)−2M1(G) (29)

KCD2(G) = 4(n−1)
(
m(n−2)−m(2n−3)

)
+ 4m2 (30)

+(5n−8)M1(G)−HM(G)

KCD2(G) = 4(n−1)(n−2)m− (4n−6)(n−1)
(
n(n−1)−4m

)
(31)

+2(n−1)2
(
n(n−1)−6m

)
+ 4m2 + nM1(G)−HM(G)

KCD2(G) = 4(n−1)(n−2)m− (4n−6)M1(G) + HM(G). (32)

Proof.

Proof of Eq. (29):

Considering Eqs. (9), (22) and (23), we have

KCD2(G) =
∑

e=uv∈E(G)

(
dG(u) + dG(v)

)
dG(e)

=
∑

e=uv /∈E(G)

(
n−1−dG(u) + n−1−dG(v)

)(
2n−4− (dG(u) + dG(v)

)
=

∑
e=uv /∈E(G)

4(n−1)(n−2)− (4n−6)
∑

e=uv /∈E(G)

(
dG(u) + dG(v)

)
+

∑
e=uv /∈E(G)

(
dG(u) + dG(v)

)2
.

By an analogous reasoning,

M1(G) =
∑

uv /∈E(G)

(
dG(u) + dG(v)

)
and HM(G) =

∑
uv /∈E(G)

(
dG(u) + dG(v)

)2
.

Thus,

KCD2(G) = 4m(n−1)(n−2)− (4n−6)M1(G) + HM(G).

In view of Eq. (14)

KCD2(G) = 4m(n−1)(n−2)− (4n−6)M1(G) + HM(G) (33)

172



KCD indices and coindices of graphs

Taking into account Eqs. (13) and (17), Eq. (33) results into Eq. (29).

Proof of Eq. (30):

In view of Eqs. (9), (25) and (26), we get

KCD2(G) =
∑

e=uv∈E(G)

(
dG(u) + dG(v)

)
dG(e)

=
∑

e=uv /∈E(G)

(
n−1−dG(u) + n−1−dG(v)

)(
2n−4− (dG(u) + dG(v)

)
=

∑
e=uv /∈E(G)

4(n−1)(n−2)− (4n−6)
∑

e=uv /∈E(G)

(
dG(u) + dG(v)

)
+

∑
e=uv /∈E(G)

(
dG(u) + dG(v)

)2
.

By Eqs. (4) and (7), it directly follows

KCD2(G) = 4m(n−1)(n−2)− (4n−6)M1(G) + HM(G) (34)

Application of Eqs. (13) and (15) to Eq. (34) yields Eq. (30).

Proof of Eq. (31):

Using Eqs. (11), (22) and (23), we have

KCD2(G) =
∑

e=uv /∈E(G)

(
dG(u) + dG(v)

)
dG(e)

=
∑

e=uv∈E(G)

(
n−1−dG(u) + n−1−dG(v)

)
(
2n−4− (dG(u) + dG(v)

)
=

∑
e=uv∈E(G)

4(n−1)(n−2)− (4n−6)
∑

e=uv∈E(G)

(
dG(u) + dG(v)

)
+

∑
e=uv∈E(G)

(
dG(u) + dG(v)

)2
.

By reasoning,

M1(G) =
∑

uv∈E(G)

(
dG(u) + dG(v)

)
and HM(G) =

∑
uv∈E(G)

(
dG(u) + dG(v)

)2
.

173



Keerthi G. Mirajkar and Akshata Morajkar

Hence

KCD2(G) = 4m(n−1)(n−2)− (4n−6)M1(G) + HM(G) (35)

Substituting Eqs. (12) and (16) in Eq. (35), simple calculation yields Eq. (31).

Proof of Eq. (32):

With the help of Eqs. (11), (25) and (26), we get

KCD2(G) =
∑

e=uv /∈E(G)

(
dG(u) + dG(v)

)
dG(e)

=
∑

e=uv∈E(G)

(
n−1−dG(u) + n−1−dG(v)

)(
2n−4− (dG(u) + dG(v)

)
=

∑
e=uv∈E(G)

4(n−1)(n−2)− (4n−6)
∑

e=uv∈E(G)

(
dG(u) + dG(v)

)
+

∑
e=uv∈E(G)

(
dG(u) + dG(v)

)2
Eq. (32) immediately follows.

2

4 KCD indices of some graph operations

In this section, we study the graph operations using KCD indices. The
well-known graph operations sum(join), cartesian product and composition of
graphs are considered. All operations considered under the context are binary,
with finite and simple graphs G and H. For the graphs G and H vertex and edge
sets are denoted by V (G) and V (H), E(G) and E(H) respectively. The detailed
information on sum(join) of graphs is refered in[Khalifeh et al., 2008a], cartesian
product of graphs studied in[Khalifeh et al., 2008b] and composition of graphs is
reported in [Imrich and Klavzar, 2000, Khalifeh et al., 2008a]. We refer [Khalifeh
et al., 2009] for detailed information about graph operations.

Sum(join):
The sum(join) G + H of two graphs G and H with disjoint vertex sets

|V (G)| and |V (H)| is the graph on the vertex set V (G) ∪ V (H) and the edge
set E(G) ∪ E(H) ∪{uv : u ∈ V (G) and v ∈ V (H)}. For the graph G + H,
|V (G+H)| = |V (G)|+V (H)|, |E(G+H)| = |E(G)|+|E(H)|+|V (G)||V (H)|,

174



KCD indices and coindices of graphs

the degree of any vertex u ∈ G + H is

dG+H(u) =

{
dG(u) + |V (H)| u ∈ V (G)
dH(u) + |V (G)| u ∈ V (H).

Theorem 4.1. Let G and H be graphs. Then

KCD1(G + H) = 2

(
M1(G) + M1(H) + |E(H)|

(
4|V (G)|−1

)
+|E(G)|

(
4|V (H)|−1

)
+|V (G)||V (H)|

(
|V (G)|+ |V (H)|−1

))
.

Proof:
By definition of sum(join) G + H of two graphs G, H and Eq. (8), we have

KCD1(G + H) =
∑

e=uv∈E(G+H)

((
dG+H(u) + dG+H(v)

)
+ dG+H(e)

)
.

Since,

dG+H(e) = dG+H(u) + dG+H(v)−2.

KCD1(G + H) = 2
∑

e=uv∈E(G+H)

(
dG+H(u) + dG+H(v)−1

)
.

KCD1(G + H) = 2
∑

e=uv∈E(H)

(
dG+H(u) + dG+H(v)−1

)
(36)

+2
∑

e=uv∈E(G)

(
dG+H(u) + dG+H(v)−1

)
+2

∑
e=uv∈{uv:u∈V (G),v∈V (H)}

(
dG+H(u) + dG+H(v)−1

)
.

Observe that,∑
e=uv∈E(H)

(
dG+H(u) + dG+H(v)−1

)
=

∑
e=uv∈E(H)

(
dH(u) + |V (G)|

+dH(v) + |V (G)|−1
)

=
∑

e=uv∈E(H)

(
dH(u) + dH(v) + 2|V (G)|−1

)
.

175



Keerthi G. Mirajkar and Akshata Morajkar

Thus, ∑
e=uv∈E(H)

(
dG+H(u) + dG+H(v)−1

)
= M1(H) + 2|V (G)||E(H)| (37)

−|E(H)|.

Similarly,∑
e=uv∈E(G)

(
dG+H(u) + dG+H(v)−1

)
= M1(G) + 2|V (H)||E(G)| (38)

−|E(G)|.

In the same way,∑
u∈V (G),v∈V (H)

(
dG+H(u) + dG+H(v)−1

)
= 2|V (H)||E(G)|+ |V (H)|2|V (G)|

+2|E(H)||V (G)|+ |V (G)|2|V (H)|− |V (G)||V (H)|.
(39)

Substituting Eqs. (37), (38) and (39) in Eq. (36) completes the proof.

2

Theorem 4.2. Let G and H be graphs. Then

KCD2(G + H) = HM(G) + HM(H) +
(
5|V (H)|−2

)
M1(G) +

(
5|V (G)|−2

)
M1(H)

+8

(
|V (G)||E(H)|

(
|V (G)|−1

)
+ |V (H)||E(G)|

(
|V (H)|−1

)
+ |E(G)||E(H)|

)

+|V (G)||V (H)|

((
|V (G)|+ |V (H)|

)2
+ 4
(
|E(G)|+ |E(H)|

)
−2
(
|V (G)|+ |V (H)|

))
.

Proof.
With the knowledge of sum(join) G+H of two graphs G, H and Eq. (9), we have

KCD2(G + H) =
∑

e=uv∈E(G+H)

(
dG+H(u) + dG+H(v)

)
dG+H(e).

As,

dG+H(e) = dG+H(u) + dG+H(v)−2.

176



KCD indices and coindices of graphs

This implies,

KCD2(G + H) =
∑

e=uv∈E(G+H)

(
dG+H(u) + dG+H(v)

)2
−2
(
dG+H(u) + dG+H(v)

)
=

∑
e=uv∈E(H)

(
dG+H(u) + dG+H(v)

)2
−2
(
dG+H(u) + dG+H(v)

)
+

∑
e=uv∈E(G)

(
dG+H(u) + dG+H(v)

)2
−2
(
dG+H(u) + dG+H(v)

)
+

∑
e=uv∈{uv:u∈V (G),v∈V (H)}

(
dG+H(u) + dG+H(v)

)2
−2
(
dG+H(u) + dG+H(v)

)
.

It follows that,

∑
e=uv∈E(H)

(
dG+H(u) + dG+H(v)

)2
−2
(
dG+H(u) + dG+H(v)

)
=

∑
e=uv∈E(H)

((
dH(u)

+|V (G)|+ dH(v) + |V (G)|
)2
−2
(
dH(u) + |V (G)|+ dH(v) + |V (G)|

))

=
∑

e=uv∈E(H)

((
dH(u) + dH(v)

)2
+ 4|V (G)|2 + 4|V (G)|

(
dH(u) + dH(v)

)
−2
(
dH(u)

+dH(v)
)
−4|V (G)|

)
.

∑
e=uv∈E(H)

(
dG+H(u) + dG+H(v)

)2
−2
(
dG+H(u) + dG+H(v)

)
= HM(H)

+4|V (G)|2|E(H)|+ 4|V (G)|M1(H)−2M1(H)−4|V (G)||E(H)|.
(40)

Similarly,∑
e=uv∈E(G)

(
dG+H(u) + dG+H(v)

)2
−2
(
dG+H(u) + dG+H(v)

)
= HM(G)

+4|V (H)|2|E(G)|+ 4|V (H)|M1(G)−2M1(G)−4|V (H)||E(G)|.
(41)

177



Keerthi G. Mirajkar and Akshata Morajkar

In the same way

∑
u∈V (G),v∈V (H)

(
dG+H(u) + dG+H(v)

)2
−2
(
dG+H(u) + dG+H(v)

)
= M1(G)|V (H)|

+M1(H)|V (G)|+ 8|E(G)||E(H)|+ |V (G)||V (H)|
(
|V (G)|+ |V (H)|

)2
+4|E(G)||V (H)|2 + 4|E(G)||V (G)||V (H)|+ 4|E(H)||V (G)||V (H)|

+4|E(H)||V (G)|2 −4|E(G)||V (H)|−4|E(H)||V (G)|

−2|V (G)||V (H)|
(
|V (G)|+ |V (H)|

)
.

(42)

Finally, the summaton of Eqs. (40), (41) and (42) gives the desired result.

2

Cartesian Product:
The cartesian product G × H of two graphs G and H has the vertex set

V (G × H) = V (G) × V (H) and e = (a, x)(b, y) is an edge of G × H if a = b
and xy ∈ E(H), or ab ∈ E(H) and x = y. For the graph G×H, |V (G×H)| =
|V (G)|V (H)|, |E(G×H)| = |E(G)||V (H)|+|V (G)||E(H)|, The degree of any
vertex (a, x) ∈ G×H is dG×H((a, x)) = dG(a) + dH(x).

Theorem 4.3. Let G and H be graphs. Then

KCD1(G×H) = 2

(
|V (G)|M1(H) + |V (H)|M1(G) + 8|E(G)||E(H)|−

(
|V (G)||E(H)|+ |V (H)||E(G)|

))
.

Proof.
In the view of definition of cartesian product G × H of two graphs G, H and Eq.
(8), we have

KCD1(G×H) =
∑

e=(a,x)(b,y)∈E(G×H)

((
dG×H((a, x)) + dG×H((b, y))

)
+ dG×H((e))

)
.

It is known that,

dG×H((e)) = dG×H((a, x)) + dG×H((b, y))−2.

178



KCD indices and coindices of graphs

Thus,

KCD1(G×H) = 2
∑

e=(a,x)(b,y)∈E(G×H)

(
dG×H((a, x)) + dG×H((b, y))−1

)
= 2

∑
a∈V (G)

∑
xy∈E(H)

(
dG(a) + dH(x) + dG(a) + dH(y)−1

)
+2

∑
x∈V (H)

∑
ab∈E(G)

(
dH(x) + dG(a) + dH(x) + dG(b)−1

)

= 2
∑

a∈V (G)

∑
xy∈E(H)

(
2dG(a) +

(
dH(x) + dH(y)

)
−1

)

+2
∑

x∈V (H)

∑
ab∈E(G)

(
2dH(x) +

(
dG(a) + dG(b)

)
−1

)

By simple reasoning we straightforwardly obtain the required result.

2

Theorem 4.4. Let G and H be graphs. Then

KCD2(G×H) = |V (G)|HM(H) + |V (H)|HM(G) +
(
12|E(H)|−2|V (H)|

)
M1(G)

+
(
12|E(G)|−2|V (G)|

)
M1(H)−16|E(G)||E(H)|.

Proof.
Taking into account the definition of cartesian product G × H of two graphs G
and H, start with Eq. (9) as

KCD2(G×H) =
∑

e=(a,x)(b,y)∈E(G×H)

(
dG×H((a, x)) + dG×H((b, y))

)
dG×H((e)).

Since

dG×H((e)) = dG×H((a, x)) + dG×H((b, y))−2.

179



Keerthi G. Mirajkar and Akshata Morajkar

We have

KCD2(G×H) =
∑

e=(a,x)(b,y)∈E(G×H)

((
dG×H((a, x)) + dG×H((b, y))

)2
−2
(
dG×H((a, x)) + dG×H((b, y))

))

=
∑

a∈V (G)

∑
xy∈E(H)

((
dG(a) + dH(x) + dG(a) + dH(y)

)2
−2
(
dG(a) + dH(x) + dG(a) + dH(y)

))
+
∑

x∈V (H)

∑
ab∈E(G)

((
dH(x)

+dG(a) + dH(x) + dG(b)
)2
−2
(
dH(x) + dG(a) + dH(x) + dG(b)

))

=
∑

a∈V (G)

∑
xy∈E(H)

((
2dG(a) + dH(x) + dH(y)

)2
−2
(
2dG(a) + dH(x)

+dH(y)
))

+
∑

x∈V (H)

∑
ab∈E(G)

((
2dH(x) + dG(a) + dG(b)

)2
−2
(
2dH(x) + dG(a) + dG(b)

))

KCD2(G×H) =
∑

a∈V (G)

∑
xy∈E(H)

(
4
(
dG(a)

)2
+
(
dH(x) + dH(y)

)2
+4dG(a)

(
dH(x) + dH(y)

)
−2
(
2dG(a) +

(
dH(x) + dH(y)

)))

+
∑

x∈V (H)

∑
ab∈E(G)

(
4
(
dH(x)

)2
+
(
dG(a) + dG(b)

)2
+4dH(x)

(
dG(a) + dG(b)

)
−2
(
2dH(x) +

(
dG(a) + dG(b)

)))
and the required result immediately follows.

180



KCD indices and coindices of graphs

2

Composition:
The composition G[H] of two graphs G and H with disjoint vertex sets

V (G) and V (H), edge sets E(G) and E(H) is the graph with vertex set V (G) ×
V (H) and (a,x) is adjacent to (b,y) whenever a is adjacent to b, or a = b and x
is adjacent to y. For the graph G[H], |V (G[H])| = |V (G)||V (H)|, |E(G[H])| =
|E(G)||V (H)|2 + |E(H)||V (G)|, The degree of any vertex (a, x) ∈ G[H] is
dG[H]((a, x)) = |V (H)|dG(a) + dH(x).

Theorem 4.5. Let G and H be graphs. Then

KCD1(G[H]) = 2
(
|V (H)|3M1(G) + |V (G)|M1(H) + 8|V (H)||E(G)||E(H)|

−|V (H)|2|E(G)|− |E(H)||V (G)|
)
.

Proof.
Using the definition of composition G[H] of two graphs G, H and Eq. (8), we
have

KCD1(G[H]) =
∑

e=(a,x)(b,y)∈E(G[H])

((
dG[H]((a, x)) + dG[H]((b, y))

)
+ dG[H]((e))

)
.

But

dG[H]((e)) = dG[H]((a, x)) + dG[H]((b, y))−2.

This implies,

KCD1(G[H]) = 2
∑

e=(a,x)(b,y)∈E(G[H])

(
dG[H]((a, x)) + dG[H]((b, y))−1

)
.

KCD1(G[H]) = 2
∑

x∈V (H)

∑
y∈V (H)

∑
ab∈E(G)

(
|V (H)|dG(a) + dH(x) + |V (H)|dG(b)

+dH(y)−1
)
+ 2

∑
a∈V (G)

∑
xy∈E(H)

(
|V (H)|dG(a) + dH(x)

+|V (H)|dG(a) + dH(y)−1
)
.

(43)

We start with

181



Keerthi G. Mirajkar and Akshata Morajkar

∑
x∈V (H)

∑
y∈V (H)

∑
ab∈E(G)

(
|V (H)|dG(a) + dH(x) + |V (H)|dG(b) + dH(y)−1

)
=

∑
x∈V (H)

∑
y∈V (H)

∑
ab∈E(G)

(
|V (H)|

(
dG(a) + dG(b)

)
+
(
dH(x) + dH(y)

)
−1

)

Thus,∑
x∈V (H)

∑
y∈V (H)

∑
ab∈E(G)

(
|V (H)|dG(a) + dH(x) + |V (H)|dG(b) + dH(y)−1

)
=

|V (H)|3M1(G) + 4|V (H)||E(G)||E(H)|− |V (H)|2|E(G)|.
(44)

Similarly,∑
a∈V (G)

∑
xy∈E(H)

(
|V (H)|dG(a) + dH(x) + |V (H)|dG(a) + dH(y)−1

)
=

4|V (H)||E(G)||E(H)|+ |V (G)|M1(H)−|V (G)||E(H)|.
(45)

Substituting Eqs. (44) and (45) in Eq. (43) generates the desired result.

2

Theorem 4.6. Let G and H be graphs. Then

KCD2(G[H]) = |V (H)|4HM(G) + |V (G)|HM(H)

+2|V (H)|2M1(G)
(
6|E(H)|− |V (H)|

)
+2M1(H)

(
5|V (H)||E(G)|− |V (G)|

)
+8|E(G)||E(H)|

(
|E(H)|−2|V (H)|

)
.

Proof.
In view of definition of composition G[H] of two graphs G, H and Eq. (9), we
start with

KCD2(G[H]) =
∑

e=(a,x)(b,y)∈E(G[H])

(
dG[H]((a, x)) + dG[H]((b, y))

)
dG[H]((e)).

It is known that,

dG[H]((e)) = dG[H]((a, x)) + dG[H]((b, y))−2.

182



KCD indices and coindices of graphs

We get,

KCD2(G[H]) =
∑

e=(a,x)(b,y)∈E(G[H])

((
dG[H]((a, x)) + dG[H]((b, y))

)2
−2
(
dG[H]((a, x)) + dG[H]((b, y))

))
.

KCD2(G[H]) =
∑

x∈V (H)

∑
y∈V (H)

∑
ab∈E(G)

((
|V (H)|dG(a) + dH(x) + |V (H)|dG(b) + dH(y)

)2
−2
(
|V (H)|dG(a) + dH(x) + |V (H)|dG(b) + dH(y)

))

+
∑

a∈V (G)

∑
xy∈E(H)

((
|V (H)|dG(a) + dH(x) + |V (H)|dG(a) + dH(y)

)2
−2
(
|V (H)|dG(a) + dH(x) + |V (H)|dG(a) + dH(y)

))
.

Thus,

KCD2(G[H]) =
∑

x∈V (H)

∑
y∈V (H)

∑
ab∈E(G)

((
|V (H)|

(
dG(a) + dG(b)

)
+ dH(x) + dH(y)

)2
−2
(
|V (H)|

(
dG(a) + dG(b)

)
+ dH(x) + dH(y)

))

+
∑

a∈V (G)

∑
xy∈E(H)

((
2|V (H)|dG(a) + dH(x) + dH(y)

)2
−2
(
2|V (H)|dG(a) + dH(x) + dH(y)

))
.

183



Keerthi G. Mirajkar and Akshata Morajkar

It follows that,

∑
x∈V (H)

∑
y∈V (H)

∑
ab∈E(G)

((
|V (H)|

(
dG(a) + dG(b)

)
+ dH(x) + dH(y)

)2
−2
(
|V (H)|

(
dG(a) + dG(b)

)
+ dH(x) + dH(y)

))

=
∑

x∈V (H)

∑
y∈V (H)

∑
ab∈E(G)

(
|V (H)|2

(
dG(a) + dG(b)

)2
+
(
dH(x) + dH(y)

)2
+2|V (H)|

(
dG(a) + dG(b)

)(
dH(x) + dH(y)

)
−2|V (H)|

(
dG(a) + dG(b)

)
−2|V (H)|dH(x)−2|V (H)|dH(y)

)

Hence,

∑
x∈V (H)

∑
y∈V (H)

∑
ab∈E(G)

((
|V (H)|

(
dG(a) + dG(b)

)
+ dH(x) + dH(y)

)2
−2
(
|V (H)|

(
dG(a) + dG(b)

)
+ dH(x) + dH(y)

))
= |V (H)|4HM(G)

+2|V (H)||E(G)|M1(H) + 8|E(H)|2|E(G)|+ 8|V (H)|2|E(H)|M1(G)
−2|V (H)|3M1(G)−8|E(H)||E(G)||V (H)|.

(46)

Similarly,

∑
a∈V (G)

∑
xy∈E(H)

((
2|V (H)|dG(a) + dH(x) + dH(y)

)2
−2
(
2|V (H)|dG(a)

+dH(x) + dH(y)
))

= 4|V (H)|2|E(H)|M1(G) + |V (G)|HM(H)

+8|V (H)||E(G)|M1(H)−8|V (H)||E(G)||E(H)|−2|V (G)|M1(H).

(47)

Finally, summation of Eqs. (46) and (47) gives the required result.

2

184



KCD indices and coindices of graphs

5 Conclusion

In this paper, we have introduced few new degree based topological indices
and coindices named KCD indices and coindices. A set of properties of these in-
dices and coindices are obtained. Finally, some graph operations are studied using
KCD indices. These results have scope for further development using remaining
graph operations.

References
Anwar Alwardi, Akram Alqesmah, R Rangarajan, and Ismail Naci Cangul. Entire

zagreb indices of graphs. Discrete Mathematics, Algorithms and Applications,
10(03):1850037, 2018.

Ali Reza Ashrafi, Tomislav Došlić, and Asma Hamzeh. The zagreb coindices of
graph operations. Discrete Applied Mathematics, 158(15):1571–1578, 2010.

Ali Reza Ashrafi, Tomislav Došlić, and Asma Hamzeh. Extremal graphs with
respect to the zagreb coindices. MATCH-Communications in Mathematical
and in Computer Chemistry, 65(1):85–92, 2011.

Kinkar Ch Das, Ivan Gutman, and Batmend Horoldagva. Comparing zagreb in-
dices and coindices of trees. MATCH-Communications in Mathematical and in
Computer Chemistry, 68:189–198, 2012.

Tomislav Došlić. Vertex-weighted wiener polynomials for composite graphs. Ars
Mathematica Contemporanea, 1(1):66–80, 2008.

Tomislav Došlic, Boris Furtula, Ante Graovac, Ivan Gutman, Sirous Moradi, and
Zahra Yarahmadi. On vertex–degree–based molecular structure descriptors.
MATCH-Communications in Mathematical and in Computer Chemistry, 66(2):
613–626, 2011.

Ivan Gutman. On hyper–zagreb index and coindex. Bulletin (Académie serbe des
sciences et des arts. Classe des sciences mathématiques et naturelles. Sciences
mathématiques), (42):1–8, 2017.

Ivan Gutman and Kinkar Ch Das. The first zagreb index 30 years after. MATCH-
Communications in Mathematical and in Computer Chemistry, 50(1):83–92,
2004.

185



Keerthi G. Mirajkar and Akshata Morajkar

Ivan Gutman and Nenad Trinajstić. Graph theory and molecular orbitals. total
ϕ-electron energy of alternant hydrocarbons. Chemical Physics Letters, 17(4):
535–538, 1972.

Ivan Gutman, Boris Furtula, Zana Kovijanić Vukićević, and Goran Popivoda. On
zagreb indices and coindices. MATCH-Communications in Mathematical and
in Computer Chemistry, 74(1):5–16, 2015.

Frank Harary. Graph theory. Addison–Wesely, Reading, Mass, 1969.

Wilfried Imrich and Sandi Klavzar. Product graphs: structure and recognition.
Wiley, 2000.

M H Khalifeh, Hassan Yousefi-Azari, and Ali Reza Ashrafi. A matrix method
for computing szeged and vertex pi indices of join and composition of graphs.
Linear algebra and its applications, 429(11-12):2702–2709, 2008a.

M H Khalifeh, Hassan Yousefi-Azari, and Ali Reza Ashrafi. Vertex and edge pi
indices of cartesian product graphs. Discrete Applied Mathematics, 156(10):
1780–1789, 2008b.

M H Khalifeh, Hassan Yousefi-Azari, and Ali Reza Ashrafi. The first and second
zagreb indices of some graph operations. Discrete Applied Mathematics, 157
(4):804–811, 2009.

K Pattabiraman and M Vijayaragavan. Hyper zagreb indices and its coindices of
graphs. Bulletin of International Mathematical Virtual Institute, 7(1):31–41,
2017.

G H Shirdel, H Rezapour, and A M Sayadi. The hyper-zagreb index of graph
operations. Iranian Journal of Mathematical Chemistry, 4(2):213–220, 2013.

Maryam Veylaki, Mohammad Javad Nikmehr, and Hamid Agha Tavallaee. The
third and hyper-zagreb coindices of some graph operations. Journal of Applied
Mathematics and Computing, 50(1-2):315–325, 2016.

Bo Zhou. Zagreb indices. MATCH-Communications in Mathematical and in
Computer Chemistry, (52):113–118, 2004.

Bo Zhou and Ivan Gutman. Further properties of zagreb indices. MATCH-
Communications in Mathematical and in Computer Chemistry, 54(1):233–239,
2005.

186