Some Results On Chemical And Network Graph Theory

All the graphs considered here are undirected and simple.In chemical graph theory, chemical molecules' space topological indices and topological properties as well as the relations between the chemical molecules' physicochemical properties and their topological indices and topological properties are studied. Chemical graph theory plays an important role in predicting and compounding new chemical substances and new medicines. In the first and the third chapter we discuss two problems concerning chemical graph theory. In the first chapter, we discuss the construction and the recognition of planar 1-cycle resonant graphs. In the third chapter, several formulas for the calculation of dissections of some special classes of trees as well as some properties of the dissections of trees are presented.In network graph theory, combinatorial optimum problems, optimum design of network and other related theoretical problems are studied. Hamiltonian problem is a world famous difficult problem in network graph theory. Up to the present day, there is still no sufficient and necessary condition for a graph to be hamiltonian. In the second chapter, we give a sufficient condition for a 4-connected graph to be Hamiltonian.The Construction and The Recognition of Planar 1-Cycle Resonant GraphsIn the topological theory of benzenoid hydrocarbons, a hexagonal system (or benzenoid system) denotes the carbon atom skeleton graph of a benzenoid hydrocarbon, which is a 2-connected plane graph whose every interior face is bounded by a regular hexagon. A Kekule structure K of a hexagonal system H is also a perfect matching of H.A hexagonal system H is normal if each of its edges lies in a perfect matching. Fuji Zhang and Rongsi Chen[l] proved that a hexagonal system H is normal if and only if every hexagon of H is resonant, that is, for any hexagon s of H there is a Kekule structure M of H such that s is an M-alternating cycle. A hexagonal system H is said to be fc-coverable if H contains at least k disjoint hexagons and, for 1 < t < k, any t disjoint hexagons of H are mutually resonant, that is, there is a Kekule structure M such that the t disjoint hexagons are M-alternating cycles.The concept of "cover" was introduced by Gutman[2]. Maolin Zheng[3] further introduced the concept of fc-coverable hexagonal systems and investigated their properties and construction. As a generalization of k-coverable hexagonal systems, Xiaofeng Guo and Fuji Zhang introduced A;-cycle resonant graphs[4].A connected graph is said to be fc-cycle resonant if, for 1 < t < k, any t disjoint cycles in G are mutually resonant, that is, there is a perfect matching M of G such that each of the t cycles is an M-alternating cycle.The concept of fc-cycle resonant graphs is useful in chemistry. It was shown in ref.[4] that in the hexagonal systems with h hexagons obtained from a same parent hexagonal system with h - I hexagons, fc*-cycleresonant systems have greater resonance energies than 1-cycle resonant systems, and also 1-cycle resonant systems have greater resonance energies than hexagonal systems not being 1-cycle resonant, where k* is the maximum number of disjoint cycles.Some necessary and sufficient conditions for a graph to be fc-cycle resonant are given in [4] and [5], and the construction of k-cycle resonant hexagonal systems are completely characterized.Theorem A[4,5]. A connected graph with at least k disjoint cycles is A;-cycle resonant if and only if G is a bipartite graph with perfect matchings and, for 1 < t < k and any t disjoint cycles C\, Ci, ... ... ..., Ct in G, G - Ui=i Ci contains no odd component.A further necessary and sufficient condition for a graph to be planar 1-cycle resonant was given by Xiaofeng Guo and Fuji Zhang[5]:Theorem B[5]. A 2-connected graph G is planar 1-cycle resonant if and only if G is bipartite and, for any cycle C in G, any bridge of C has exactly two attachment vertices which have different colors.Theorem C[5]. A 2-connected graph G is planar 1-cycle resonant if and only if G is...