On Some Problems Of Graph Theory In Chemistry And Networks

As we know, the word "graph" in "Graph Theory" has many meanings. Therefore, graph theory has many applications in many fields. For example, let G = (V, E) be a simple undirected graph, if each vertex and edge in G represent an atom in a molecule and chemical bond between atoms, respectively, then this kind of graphs are called molecular graphs. One of the most active fields of research in contemporary chemical graph theory is the study of topological indices, or graph invariants, that can be used for describing and predicting physicochemical and pharmacologic properties of organic compounds. Since 1947, when H. Wiener conceived the first molecular topological index, eventually named the "Wiener index", hundreds topological indices including the Randic index and its generalization have been considered in the mathematical and/or chemical literature. Here, the general Randic index for a graph is defined aswhere d(u) denotes the degree of the vertex u and α≠0 is a real number. In particular, w_-1/2 (G) is called the Randic index of graph G.Besides that just mentioned, it is well-known that a network is modeled as a connected (directed or undirected) graph, with vertex representing processors and edges representing communication links. The study of fault-tolerant routings is one important direction of research in graph theory related to networks. Let x and y be two different vertices of a (strongly) connected (directed) graph G. Denote by P_G(x, y) the set of all (x, y)-paths in G. Let P(G) = {P_G{x, y) : x, y ∈ V, x≠ y} and B = V × V\{(x,x) : x ∈ V}. We define the routing ρ as a map from B to P(G) with ρ(x,y) ∈ P_G(x,y), that is, the map ρ assigns every pair (x,y) of vertices in B an (x,y)-path, i.e. ρ(x,y). ρ(x,y) is usually called a route. It is assumed that the routing ρ is computed only once for a given communication network configuration, and thus all messages must be sent by using those routes assigned by ρ. When a vertex or an edge (arc) fails, the routes that go through it become unusable. However, communication is still possible through a sequence of surviving routes. In order that the communication does not become too long, it is important that the number of routes to be concatenated is as small as possible. Consider a communication network G with a fixed routing ρ in which vertex and edge or arc faults F might occur. The diameter D(R(G, ρ)/F) of the surviving route graph could be an important measurement for the fault-tolerance of the network. It directly reflects the delay of sending messages.In this thesis, we mainly study the Randic index as well as its generalization...