Degrees, Edges And Cycles In Graphs

In 1736, Euler published the earliest known paper on graph theory, in which he studied the seven bridges problem of Konigsberg which led to a new subject-Graph Theory. Since 1960s, graph theory has experienced explosive growth. Meanwhile, it led to a lot of interesting problems of graph theory, such as the hamiltonian problem, the coloring problem, the connectivity problem, the matching problem and so on. Along with the development of graph theory, its results are being applied more and more in many areas of the information, chemistry, social and natural sciences. At present, graph theory has become a very useful and practical subject.For a graph G, it is called a hamiltonian graph or hamiltonian if G has a hamil-tonian cycle, i.e. a cycle containing all vertices of G. This concept was proposed by Sir W.R. Hamilton as a mathematical game. The hamiltonian problem:determining when a graph is hamiltonian, has long been fundamental in graph theory. From 1970s, the hamiltonian problem has been considered widely because of its relation with the Four Color Theorem and its rich properties in graph structure theory, extremal graph theory, and its development under stimulation of applications in networks and the theory of complexity and so on. Since it is a NP-complete problem that determining whether a graph is hamiltonian, looking for the sufficient conditions for a graph being hamiltonian is a main direction for many scholars.Let G=(V(G),E(G)) be a simple graph. V(G) and E(G) are called vertex set and edge set of G respectively. The cardinality of V(G) is called the order of G. For any vertex v in G, the degree d(v) of v is the number of vertices adjacent to v in G. Let d(u,v) be the distance between vertices u and v in G. Define N1(v)= N(v)= {u∈V(G):d(u,v)= 1} and N2(v)={u∈V(G):d(u,v)= 2}. Basing on the concept, of degrees, Zhu, Li and Deng introduced definitions of two implicit degrees id1(u) and id2(v) for a vertex u. We call id1(u) and id2(v) the first implicit degree and the second implicit degree of a vertex u respectively. Firstly let's have a look at the definition of the first implicit degree for a vertex v. (a)If N2(v)≠0 and d(v)≥2,denote by M2=max{d(u):u∈N2(v)}. Let d(v)=l+1 and d1≤d2≤d3≤…≤dl≤dl+1≤…be the degree sequence of the vertices of N1(v)∪N2(v).Put Then the first implicit degree of v is defined as id1(v)=max{d(v),d*(v)}.(b)If N2(v)=(?)or d(v)<2,then define id1(v)=d(v).It is clear from the definition that id1(v)≥d(v).For the definition of the second implicit degree of a vertex v,it just needs to change d*(v)of the definition of the first implicit degree into where m2=min{d(u):u∈N2(v)}.Obviously,id2(v)≥id1(v)≥d(v).In Section one of Chapter two,we will discuss the hamiltonicity of graphs on a second implicit degree condition.In 1952,Dirac first showed that if the degree of every vertex is at least half of the order of a graph whose order is at least 3,then the graph is hamiltonian.The result is called Dirac theorem and the condition is called Dirac condition.Since then,various sufficient conditions for a graph to be hamiltonian have been given in terms of vertex degree conditions in generalization of Dirac theorem.In 1960,Ore first extended it and showed that a graph G of order n≥3 is hamiltonian if d(u)+d(v)≥n for any pair of nonadjacent vertices u and v in G.This conclusion is named Ore theorem and the condition is called Ore condition. Bondy considered more nonadjacent vertices and then generalized Ore theorem in 1980 by proving that a k-connected graph G of order n≥3 is hamiltonian if the degree sum of any k+1 independent vertices is greater than(k+1)(n-1)/2.In Section one of Chapter two.we will refer to the second implicit degrec and generalize the result of Bondy by showing that a k-connected graph G of order n≥3 is hamiltonian if the second implicit degree sum of any k+1 independent vertices is greater than(k+1)(n-1)/2.Let X be a vertex subset of G. X is cyclable in G if there is a cycle in G containing all vertices of X. If we take X=V(G), then X being cyclable is equivalent to G being hamiltonian. Hence we may regard hamiltonian problem as a special case of cyclable problem.In Section two of Chapter two, we will study the cyclability of graphs on the first implicit degree condition. Ota generalized Ore theorem by considering the cyclability of any vertex subset X of G under Ore type condition. Flandrin, Li, Marczyk and Wozniak in 2005 extended the conclusion of Ota under the condition called regional Ore's condition. In Section two of Chapter two, we will generalize the result of Flandrin et al. with a first implicit degree condition. More precisely, we obtain that X is cyclable in a k-connected graph G if the first implicit degree sum of any pair of nonadjacent vertices u and v in each Xi is at least the order of G, where each Xi. i=1,2....,k, is a vertex subset of G and X=∪i=1k XiIf we put a non-nogative number w(e) to e for each edge e of a graph G, then we call G a weighted graph and w(e) the weight of e. The weighted degree dw(v) of a vertex v in G is the sum of the weights of the edges incident with v. For a subgraph H of G, we denote by w(H) the weight of H equalling to the sum of weights of the edges in H. An unweighted graph can be regarded as a weighted graph in which each edge has weight 1. Motived by the definition of the second implicit degrees, Li gave a definition of implicit weighted degree idw(v) for a vertex v with idw(v)≥dw(v) in weighted graphs. It only needs to extend the definition of the second implicit degree to weighted graphs directly.In Chapter three, we will consider the weight of heavy cycles (cycles with large weight) on implicit weighted degree condition in weighted graphs. In 2001. Zhang, Li and Broersma gave lower bounds of weights of heavy cycles C in some 2-connected weighted graphs. In Chapter three, we will present an analogous result on the implicit. weighted degree condition, and hence generalize their result.It is an important subject on the fault-tolerance problems in networks. In Chap- ter four, we will deliberate this problem. In 2009, Hu and Li proved removable match-ings and hamiltonian cycles. Motived by this result and working on Ore condition, we extend this conclusion. For a graph G satisfying Ore condition and a subgraph H C G with maximum degreeΔ(H)< 2 and the size of edge set|E(H)|=k, we show the following two results:(1) If G-E(H) is 2-connected and n≥4k+3, then G-E(H) is hamiltonian with some exceptions. (2) If G-E(H) is 2-connected, n≥2k+5 and H is a cycle, then G-E(H) is hamiltonian with some exceptions.