Graph entropy and operation

Changwu Song

September 26, 2024

1 Introduction

Graph entropy is a measure of information in graphs. It is closely related to graph parameters and
structural characteristics, and it has significant applications in fields such as chemistry, biology, trans-
portation and communications, and social sciences. Researching the e↵ect of graph entropy under
graph operations is very meaningful. As a measure of graph information, investigating the changes
in graph entropy after graph operations can further explore the relationships between graph entropy,
graph parameters, and graph structure.

1.1 Shannon entropy

Let p = (p1 , p2 , P
. . . , pn ) be the probability distribution associated with the vertices of a graph, where
n
0  pi  1 and i=1 pi = 1. The Shannon entropy , I(P ), is given by:
n
X
I(P ) = pi log pi
i=1

Consider a graph G = (V, E) consisting of n vertices and m edges, where each vertex v 2 V has a
degree d(v). The probability distribution associated with the vertices is given by:

f (vi )
p(vi ) = Pn
j=1 f (vj )

where f (vi ) represents an information function associated with vertex vi , and the sum of p(vi ) over all
vertices equals one.

The entropy of the graph G, denoted as If (G), is then expressed as:

n
!
X f (v ) f (v )
If (G) = Pn i log Pn i
i=1 j=1 f (vj ) j=1 f (vj )

1.2 Entropy based on degree

Given the power index k in degree-based entropy, the entropy Idk (G) of a graph G is defined as follows,
where G contains n vertices v = (v1 , v2 , . . . , vn ) and dG (vi ) denotes the degree of vertex vi :
n
X d (v )k dG (vi )k
Idk (G) = Pn G i k
log P n k
i=1 j=1 dG (vj ) j=1 dG (vj )

1
This measure reflects the weight of each vertex’s degree relative to the total degree, allowing for a
scaled comparison of degree influence across the graph.

For k = 1, the degree-based entropy Id (G) simplifies to:

n
1 X
Id (G) = log(2m) dG (vi ) log[dG (vi )]
2m i=1

Here, 2m represents twice the number of edges, acknowledging each edge contributes two degrees,
hence providing a normalization against the total number of vertices.

1.3 Entropy based on the number of independent sets

Calculating the entropy of graphs based on the number of independent sets:

n
X ik (G) ik (G)
Inis (G) = log
(G) (G)
k=0

Here, ik (G) denotes the number of independent sets of size k in G, and (G) is the total number of
independent sets in the graph.

1.4 Entropy based on the number of matchings

The entropy of a graph G based on the number of matchings is defined as:

m
X zk (G) zk (G)
Inm (G) = log
Z(G) Z(G)
k=0

where zk (G) represents the number of matchings of size k in G, and Z(G) represents the total number
of matchings in G.

This measure considers the entire matching structure of G and provides a detailed view of how match-
ings distribute across the graph. The matching structure of a graph G is a subset M of edges such
that no two edges share a vertex.

1.5 Entropy based on vertex coloring

Consider a graph G = (V, E) with n vertices and m edges. Each vertex v in V is unique, and E
denotes the edges. The vertex set V can be partitioned into k disjoint subsets, V1 , V2 , . . . , Vk , each of
which forms a component of the graph without any internal connections; thus, each set Vi represents
a complete connected component of G without internal edges.

For each vertex x, where x 2 V and for i = 1, 2, . . . , k, the vertex x is exclusively part of one of the
sets V1 , V2 , . . . , Vk , forming the graph’s substructures. Each Vi contributes to the graph’s entropy.

the entropy based on vertex coloring Ic (G) for graph G is defined as:
( k )
X |Vi | |Vi |
Ic (G) = min log
V0
i=1
n n

where |Vi | represents the number of vertices in each subset Vi , and n is the total number of vertices
in G. The expression calculates the minimal entropy based on the distribution of vertices across the
subsets.

2
2 Graph operation

2.1 Symmetric di↵erence

L
Let G and H be two graphs. The symmetric di↵erence G H is defined as follows:

L
• The vertex set of G H is given by:
M
V (G H) = {(a, b) | a 2 V (G), b 2 V (H)}

L
• The edge set of G H is given by:
M
E(G H) = {((a, b), (c, d)) | (ac 2 E(G) and b = d) or (a = c and bd 2 E(H))}

2.2 Cartesian product

For graphs G and H, the Cartesian product G ⇥ H is defined by:

• The vertex set of G ⇥ H is given by:

V (G ⇥ H) = {(a, b) | a 2 V (G), b 2 V (H)}

• The edge set of G ⇥ H is given by:

E(G ⇥ H) = {((a, b), (c, d)) | ac 2 E(G) and bd 2 E(H)}

2.3 Tensor product

N
For graphs G and H, the Tensor product G H is defined as follows:

N
• The vertex set of G H is given by:
O
V (G H) = {(a, b) | a 2 V (G), b 2 V (H)}

N
• The edge set of G H is given by:
O
E(G H) = {((a, b), (c, d)) | (ac 2 E(G) and bd 2 E(H))}

2.4 Corona product

For graphs G and H, the Corona product G H is defined by:

• The vertex set of G H is given by:

V (G H) = {(ui , vj ) | i = 1, 2, . . . , n; j = 0, 1, . . . , n2 }

• The edge set of G H is given by:

E(G H) = {((ui , v0 ), (uk , v0 )) | ui uk 2 E(G)}[{((ui , vj ), (ui , vj+1 )) | vj vj+1 2 E(H), i = 1, 2, . . . , n}[{((ui , v0 ), (ui ,

3
 2.5 Adding an edge between vertex

Consider graph G and a pair of non-adjacent vertices u and v, where u 6= v. Let G0 = G + uv denote
the graph obtained by adding the edge uv to G.

2.6 Adding a pendant edge

3
. What has been studied :

Dong. Y, Qiao. S, Chen. B, et al, Maximum values of degree-based entropies of

3 . 1 bipartite graphs
-

3 2 .
Cao. S, Dehmer. M, Shi. Y. Extremality of degree-based graph entropies[J],
Information Sciences, 2014, 278:[Link] the extremal graphs for trees, unicyclic graphs, bicyclic graphs, chemical trees, and chemical graphs when
k=1

3 3 Chen. Z, De. Hmer. M, Shi. Y, Bounds for degree-based network entropies[J], Elsevier
Science
.

Inc. 2015

3 .

4 Hu. D, Li. X. L, Liu. X. G, Zhang, S. G, Extremality of Graph Entropy Based on Degrees

of Uniform Hypergraphs with Few Edges[J], Acta Math. Sin. 2019, 35, 1238–1250.

--

4
. What I to
study
:
want

Degree-based entropy of Hypergraphs after operations

·
some

coloring-based entropy of Hypergraphs (after

some
operations
values (maybe R-
Hypergraphs
Try
to extreme
give
some

4 for some small

b)
 entropies
to

coloring
more
weak
Strong coloring ; ; Extend
Hypergraphs .

models method
5 .

Meaning Giving
:
more
analysis or

for hypergraphs or
graphs .
In network ?

chemical areas .

11