Some Properties Of Graphs Under Implicit Degree Conditions

The study of graph theory started from1736, Euler solved the seven bridges problem of Konigsberg by graph method, and published the earliest known pa-per on graph theory. Since then, Graph Theory came into being. Since1960s, graph theory has developed quickly and numerous results on graph theory sprung forth. Meanwhile, it led to a lot of interesting problems in graph theory, such as Hamilton problem, Chinese postman problem, coloring problem, connectivity problem, matching problem and so on. Moreover, graph theory is widely applied to solve problems in chemistry, biology, computing science and other disciplines. In addition, graph theory also has a wide range of applications in the fields of engineering and social sciences.A cycle in a graph G is called a hamiltonian cycle if it contains all vertices of G. And G is called a hamiltonian graph or hamiltonian if it contains a hamilto-nian cycle. The concept of hamiltonian cycle is named after W.R. Hamilton who proposed it as a mathematical game. And a classical problem in graph theory, i.e. Hamilton problem (determining whether a graph is hamiltonian or not) was induced by the game. The Hamilton problem contains a series of problems:such as hamil-tonian cycles, hamiltonian paths, the circumference of graphs, the paneyclicity of graphs, dominating cycles and the relative length of longest paths and longest cy-cles. From1970s, the Hamilton problem has been considered widely because of its relationship with Four Color Theorem and its rich properties in graph structure the-ory, extremal graph theory and so on. Moreover, the theory of hamiltonian cycles is widely used in networks and the theory of complexity. Since Hamilton problem is a NP-complete problem, looking for sufficient conditions for a graph to be hamiltonian is a main direction for many scholars.All the graphs considered in our work are simple and undirected. Let G=(V(G), E(G)) be a simple graph, with vertex set V(G) and edge set E(G). The cardinality of V(G) is called the order of G. For a vertex v in G, the degree, denoted by d(v) and the neighborhood, denoted by N(v) of v, are defined as the number and the set of vertices in G which are adjacent to v, respectively. Let d(u,v) be the distance between vertices u and v in G. We use N2(v) to denote the vertices in G which are at distance2from v.Some vertices may have small degrees. Then we hope to use some large de-gree vertices to replace small degree vertices in the right position considered in the proofs, so that we may construct a longer cycle. Inspired by the idea, Zhu, Li and Deng introduced the definition of the first implicit degree, denoted by id1(v) and the definition of the second implicit degree, denoted by id2(v) for a vertex v. Let m2=min{d(u):u∈N2(v)} and M2=max{d(u):u∈N2(v)}. Set k=d(v)-1and suppose d1≤d2≤d3≤...≤dk≤dk+1≤... is the degree sequence of vertices of N(v)U N2(v).(a) If N2(v)≠φ and d(v)≥2, then id1(v) and id2(v) are defined by:(b) If N2(v)=φ or d(v)<2, then define id2(v)=id1(v)=d(v).It is clear from the above definitions that id2(v)> id1(v)> d(v) for every vertex v.A graph G is called pancyclic if it contains cycles of each length l with3≤l≤|V(G)|. Clearly, any bipartite graph is not pancyclic. Moreover, a pancyclic graph is certainly hamiltonian, but not conversely. A cycle C in G is called a dominating cycle if each component of G-C is an independent vertex, i.e. each edge in G is incident with at least one vertex of C.In this thesis, we discuss hamiltonian cycles, pancyclicity of graphs, dominating les and the relative length of longest paths and longest cycles of graphs. We construct our work in five chapters. A short but relatively complete instruction is given in Chapter one. First, we give some basic definitions and notations. Then we describe some progress about the above four topics and outline the main results of this thesis.In Chapter two, we consider the hamiltonicity of graphs under the second implicit degree condition and give a sufficient condition for a graph to be hamiltonian. We prove that:Let G be a2-connected graph of order n≥3, if the second implicit degree sum of each pair of vertices at distance2is more than or equals to n-1, then G is hamiltonian with some exceptions.In Chapter three, we discuss the pancyclicity of graphs on the second implicit degree condition and give a sufficient condition for a graph to be pancyclic. In1971, Bondy proved that:Let G be a graph of order n≥3, if the degree of each vertex is more than or equals to n/2, then G is either pancyclic or isomorphic to the complete bipartite graph Kn/2,n/2.Furthermore, he suggested a mela-conjecture that almost any nontrivial condition on a graph which implies that the graph is hamiltonian also implies that the graph is pancyclic.(There may be a simple family of exceptional graphs). According to this conjecture, we prove that:Let G be a2-connected graph of order n≥3, if the second implicit degree of each vertex is more than or equals to n/2, then G is pancyclic unless G is bipartite, or else n=4r,r≥2and G is F4r. Moreover, we show our result is more useful than Bondy’s result by using some examples.In Chapter four, we discuss the dominating cycles of graphs under implicit degree condition and give a sufficient condition for each longest cycle of a3-connected claw-free graph to be a dominating cycle. First, we give another definition of implicit degree based on the definitions of implicit degrees given by Zhu, Li and Deng.(a) If N2(v)≠0and d(v)≥3, then the implicit degree, denoted by id0(v) of v, is defined by: (b) If N2(v)=φ or d(v)≤2, then define id0(v)=d(v).It is clear from the above definition that id0(v)> d(v) for each vertex v.Since it is difficult to obtain the sufficient conditions for a graph to be hamiltonian by considering the degree sum of four or more independent vertices, many authors turn to investigating sufficient conditions for a graph to contain a dominating cycle and the relationship between dominating cycles and longest cycles. Nash-Williams gave a sufficient condition for each longest cycle of a2-connected graph to be a dominating cycle. He proved that:Let G be a2-connected graph of order n, if the degree of each vertex is more than or equals to (n+2)/3, then each longest cycle in G is a dominating cycle. We study the analogous problems in graphs under implicit degree condition. In fact, we show that if G is a3-connected claw-free graph of order n such that id0(v)≥(n+2)/3for each vertex v, then each longest cycle in G is a dominating cycle. Moreover, we show the connectivity in our result is best possible and our result is more useful than Nash-Williams’result in some sense.In Chapter five, we are interested in the relative length of long paths and cycles in graphs. For a graph G, we denote by p(G) and c(G) the number of vertices of a longest path and a longest cycle in G, respectively. Enomoto, Heuvel, Kaneko and Saito proved that:Let G be a connected graph of order n such that the degree sum of any three independent vertices is more than or equals to n, then either G contains a hamiltonian path, or c(G)≥p(G)-1. We study the analogous problems in graphs, and obtain that:Let G be a2-connected graph on n vertices such that the second implicit degree sum of any three independent vertices is more than or equals to n+1, then either G contains a hamiltonian path, or c(G)≥p(G)-1. Furthermore, we show the connectivity and the low bound in our result are best possible and our result is more useful by using some examples.