Randi(?) Index And Cycles In Graphs And Applications

All graphs considered in this thesis will be simple. Let G be a graph. A Hamilton cycle is a cycle which contains all vertices of the graph. A graph G is called Hamiltonian if G has a Hamilton cycle. Hamiltonian problem has been studied widely in emphasizing both its relation with the Four Color Theorem until 1970's and its rich properties in extremal graph theory, graph structure theory, etc. Moreover, it develops under stimulation of applications in telecommunication networks and the theory of complexity. Determining whether Hamilton cycles exist in graphs is NP-complete. Therefore it is natural to study sufficient conditions for hamiltonicity.Dirac had been one of the leading graph theorists. He developed methods of great originality and made many fundamental discoveries. He showed in 1952 [36] that if the degree of every vertex is at least half of the order of the graph, the graph is Hamiltonian. This approach taken to develop sufficient conditions for a graph to be Hamiltonian usually involved some sort of degree conditions. Since 1952, many results have been obtained by various peoples in generalization of Dirac's theorem and now. this area is one of the core subjects in Hamiltonian graph theory and extremal graph theory. Matthews and Sumner [101] investigated the degree conditions for hamiltonicity in 2-connected claw-free graphs. Li, Lu and Liu [76] studied 3-connected claw-free graphs. Some vertices may have small degrees. Then we want to use some large degree vertices to replace small degree vertices in the right position considered in the proofs, so that we may construct a long cycle. This idea leads to the definition of implicit degree, which was introduced by Zhu, Li and Deng [141]. Let G be a graph and let v be a vertex of G with degree d(v)=k+1 for some integer k≥0. Let N1(v)=N(v)={x∈V(G)|xv∈E(G)} and let N2(v)={x∈V(G)|d(x,v)=2}, where d(x, v) denotes the distance between x and v in G, i.e., the length of a shortest (x,v)-path in G. If N2(v)≠(?), we define M2v= max{d(x)|x∈N2(v)}. Let d1v≤d2v≤...≤dkv≤dk+1v≤denote the degree sequence of the vertices of N1(v)∪N2(v). Then the implicit degree of v, denoted by d1(v), is defined as follows:if dk+1v＞M2v or if N2(v)=(?), then d1(v)=max{dk+1v, k+1}; otherwise d1(v)=max{dkv, k+1}. It is clear from the definition that d1(v)≥d(v) for every vertex v. In [141], Zhu, Li and Deng gave a generalization of Dirac's Theorem on minimum implicit degree condition. Under the condition of Matthews's Theorem [101], we consider the implicit degree conditions for hamiltonicity in 2-connected claw-free graphs in Chapter 2.Another generalization of Hamiltonian graphs is the idea of cyclable sets. A subset S of V(G) is called cyclable in G if all the vertices of S belong to a common cycle in G. There are many results concerning the union of degree sums and neigh-borhood conditions of independent vertices for hamiltonicity, for example in [13], [36], [56], [106] and [118] et al. Cyclability is a natural generalization of hamiltonic-ity since clearly, if S=V(G), "S is cyclable" is equivalent to "G is Hamiltonian". So there are some related results concerning the union of degree sums and neigh-borhood conditions of independent vertices for cyclability, see [11], [18], [42], [56] and [107] et al. We consider the sufficient conditions on four independent vertices for cyclability in Chapter 3.If each edge of G is assignd a color, then G is an edge-colored graph. We denote dc(v) the color degree of a vertex v, be defined as the maximum number of edges incident with v, that have distinct colors. A subgraph H of G is called heterochromatic, or rainbow, or multicolored if any pair of edges in H have distinct colors. This kind of subgraphs has received increasing attention in the past decade. Cycles and paths are among the basic research fields of graph theory, thus it is of special interests to study the heterochromatic cycles and paths in edge-colored graphs. The main focus of Chapter 4 is to consider the heterochromatic cycle or path problems. Let HCl denote a heterochromatic cycle with length l. Li and Wang [84] showed that if dc(v)≥(n+1)/2for every vertex v of an edge-colored graph, there exists a heterochromatic cycle. In [30], Chen and Li conjectured that if G is an edge-colored graph with dc(v)≥k≥3 for any v∈V(G), then G has a heterochromatic path of length at least k-1. And in the same paper, they proved the case 3≤k≤7. In [31], it is showed that if G is an edge-colored graph with dc(v)≥k≥7 for any v∈V(G), then G has a heterochromatic path of length at least「(2k)/3」+1. We study HC4 in triangle-free graphs and bipartite graphs under color degree conditions and consider about heterochromatic paths in an edge-colored bipartite graphs.The last part of the thesis is devoted to another active area of graph the-ory, chemical graph theory. Graph theory has many applications in the chemical field, the winner of the Nobel Prize in Chemistry in 1975, Professor Vlado Prelog has repeatedly stressed the importance of graph theory applied to chemistry. The molecular structure of chemical molecules in the layers of energy can be expressed using graph theory. Two kinds of correspondence between graphs and chemical categories have found numerous applications in chemistry:i) A graph corresponds to a molecule, i.e., points symbolize atoms and lines symbolize chemical covalent bonds. These may be called structural or constitutional graphs, ii) A graph cor-responds to a reaction mixture, i.e., points symbolize chemical species and lines symbolize conversions between these species. These may be called reaction graphs. The former type of graph gave Cayley the incentive to derive a procedure for counting the constitutional isomers of alkanes and later it led Polya towards the discovery of his powerful counting theorem. Thus, chemistry is an acknowledged origin for the beginning and development of graph theory. Topological indices are one of the important branches in chemical graph theory. Topological indices are numerical quantities derived from molecular graphs representing molecules. The Randic index of an organic molecule whose molecular graph is G was introduced by the chemist Milan Randic in 1975 [114] as R(G)=∑uv 1/(d(u)d(v))^1/2, where d(u) and d(v) stand for the degrees of the vertices u and v, respectively, and the summation goes over all edges uv of G. This topological index, sometimes called connectivity index, has been successfully related to physical and chemical properties of organic molecules and become one of the most popular molecular descriptors. This is the only topological index to which four books [52,71,72,88] are devoted. Bollobas and Erdos [12] gave the sharp lower bound of R(G)≥(n-1)^1/2 when G is a graph of order n without isolated vertices. People gave the sharp lower and upper bounds on the Randic index of special graphs, see [38], [46], [90], [109] and [133] et al. There are plenty of graph parameters related to the Randic index, for example, degree, matching, girth, diameter et al. In [5], Aouchiche, Hansen and Zheng proposed a conjecture related with girth, we give sharp lower bounds of Randic index of unicyclic and bicyclic graphs with girth g which partly confirm the conjecture. We also deal with conjugated bicyclic graphs (bicyclic graphs with perfecting match-ing), and give a sharp lower bound on the Randic index of bicyclic graphs with a given size of matching.