Extremal Problems Related to the Study of Graph Indices
No Thumbnail Available
Date
2020-07-19
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Addis Ababa University
Abstract
Molecular descriptors called topological indices are graph invariants that play
a signi_cant role in chemistry, materials science, pharmaceutical sciences and
engineering, since they can be correlated with a large number of physico-
chemical properties of molecules. Topological indices are used in the process
of correlating the chemical structures with various characteristics such as
boiling points and molar heats of formation. Graph theory is used to char-
acterize these chemical structures.
Binary and m-ary trees have extensive applications in chemistry and com-
puter science, since these trees can represent chemical structures and var-
ious useful networks. In this thesis, we present exact values of all im-
portant distance-based indices for complete m-ary trees and we introduce
the general eccentric connectivity index of a graph G which is de_ned as,
ECI_(G) =
P
v2V (G) eccG(v)d_
G(v) for _ 2 R, where V (G) is the vertex set
of G, eccG(v) is the eccentricity of v and dG(v) is the degree of v in G.
The thesis consists of four chapters. In the _rst chapter we de_ne the stan-
dard graph theory concepts, and introduce the distance-based graph invari-
ants called topological indices. We give some background to these mathe-
matical models, and show their applications, which are mainly in chemistry
and pharmacology. To complete the chapter we present some known results
which will be relevant to our work.
Chapter 2 focuses on the most common distance-based indices of complete
m-ary trees of a given height. We present exact values of all important
distance-based indices for complete m-ary trees of a given height. We solve
recurrence relations to obtain the value of the most well-known index called
the Wiener index. New methods are used to express the other indices (the
degree distance, the eccentric distance sum, the Gutman index, the edge-
Wiener index, the hyper-Wiener index and the edge-hyper-Wiener index) as
well. Values of distance-based indices for complete binary trees are corollaries
of the main results.
Chapter 3 focuses on the general eccentric connectivity index of trees. We
obtain lower and upper bounds on the general eccentric connectivity index
for trees of given order, trees of given order and diameter, and trees of given
order and number of pendant vertices. The upper bounds for trees of given
order and diameter, and trees of given order and number of pendant vertices
hold for _ > 1. All the other bounds are valid for 0 < _ _ 1 or 0 < _ < 1.
We present all the extremal graphs, which means that our bounds are best
possible.
Chapter 4 focuses on the general eccentric connectivity index of unicyclic
graphs. We obtain sharp lower and upper bounds on the general eccentric
connectivity index for unicyclic graphs of given order, and unicyclic graphs
of given order and girth. All the lower bounds are valid for 0 < _ < 1 and
all the upper bounds are valid for 0 < _ _ 1.
We use combinatorial methods, algebraic methods, analytic methods and
various graph theoretical techniques, which, in combination with our ideas
yield new results.
Description
Keywords
Extremal, Problems Related, Study, Graph Indices