Wiener Index Of Oriented Graphs And Extremal Problems On Several Topological Indices

The Wiener index of a graph G is defined as the sum of distances between all pairs of vertices of G.Recently the concept of Wiener index was extended to digraphs which are not-necessarily strongly connected.This extension could be applicable in the topics of directed large networks.An orientation of a graph G is a directed graph obtained by assigning a direction to each edge of G.M.Knor et al.conjectured that for a graph G,the minimum Wiener index of G is achieved for a c(G)-coloring-induced orientation.In chapter 1,we introduce the history of development on Wiener index of directed graph and several degree-based topological indices,our research problems and main results.In chapter 2,we introduce two useful concepts,I-vertex and Wiener increment.We find that there exist some graphs which do not satisfy the coloring-induced orientation conjecture.Furthermore,we conjecture that for any positive integer k(k 33),there exists a 3-colorable graph G such that the minimal Wiener index orientations of G have a directed path of length k,and we prove it for k ?6.In chapter 3,we concentrate on the minimum Wiener index orientations of general graphs.We give some basic results and get the minimum orientations of two bicyclic graphs.In chapter 4,we discuss graphs with large Randi? index.We determine the greatest Randi? index of n-vertex tricyclic graphs contained pendent vertices,the first up to sixth greatest Randi? index of general tricyclic graphs and characterize the corresponding extremal graphs.In chapter 5,we consider the extremal problems of harmonic index.We give the first six n-vertex tricyclic graphs with greatest harmonic indices and also give the characterization on extremal graphs.