Heavy Cycles In Weighted Graphs And Dirac-type Condition

The Hamiltonian problem is one of the three difficult problems in graph theory. If a long cycle in a graph contains all its vertices, then it is exactly a Hamilton cycle. So studying the existence of long cycles is an important approach for attacking the Hamilton problem.The minimum degree condition (called Dirac's condition) obtained by Dirac in 1952 started the study on the existence of long cycles, and there have been many achievements in this field up to now. The following aspects are mainly focused on: (1) Dirac-type conditions on the existence of long cycles in graphs; (2) Ore-type conditions on the existence of long cycles in graphs; (3) the existence of long cycles with some special properties in graphs.Since 1980, many graph theorists such as J.A.Bondy, B.Bollobas, H.J.Broersma and Fan Genghua etc. have been studying the existence of heavy cycles in weighted graphs and gained a lot of important results.The first section of this paper gives a brief introduction about the basic concepts, terminology and symboles which are used in this paper. In Section 2, we give an accurate discussion about the structure of a kind of graphs in [6] and getthe extremal graph. In the third section, we introduce a new concept----implicitweighted degree and using it we give a condition on the existence of heavy cycles in weighted graphs. We obtain a Dirac-type condition on the existence of the heavy cycle containing two prescribed vertices in weighted graphs in the last section.All graphs considered in this paper are simple. Let G = (V(G), E(G)) be a graph, where V(G) and E(G) denote the vertex set and edge set of G respectively. We use NG(V) and do(v) to denote the set and the number of neighbors of v inG respectively, and denote by NI(V) the set of vertices with distance 2 from u, by dc(u,v) the distance between u and v in G. A v-longest path is a longest path ending at v. An (a;, y)- cycle is a cycle passing through vertices x and y.A graph G is called a weighted graph if each edge e is assigned a non-negative number w(e), called the weight of e. We define the weighted degree of v byThe weight of a subgraph H of G is defined byThe one with maximum weight among a certain kind of subgraphs is also called heaviest. So a heaviest cycle is a cycle with maximum sum of all edge's weights among all cycles of a graph.In this paper, we introduce the concept of implicit weighted degree. Let v be a vertex of a weighted graph G with and d(v) 2; let / = d(v)-1, and let d be the weighted degree sequence of N(v) U N(v). Defineand idw(v) = max{dw(v), d*w(v)}. If N2(v) = or d(v) 1, define idw(v] = dw(v). We call idw(v) the implicit weighted degree of v.An unweighted graph can be regarded as a weighted graph in which each edge is assigned weight 1. Thus w(H) =(v) = d(v), a heaviest cycle and a heaviest v-longest path are simply a longest cycle and a y-longest path respectively. The implicit weighted degree ic is just implicit degree id(v) (see e.g.[9])The following two theorems play a basic role in the study of this paper.Theorem A Let G be a 3-connected graph and d 3 an integer, let x, y be two distinct vertices of G. Suppose d(v) d for all v ?V(G)\x, If G has at least Id vertices, then G has an (x,y)-cycle of length at least Id.Theorem B^ Let G be a 2-connected nonhamiltonian graph such that max{idw(u), idw(v)} if d(u, v) = 2. Then G contains a y-longest path P(x0, y) such that d(x0) if G has one.We discuss the structure of graph satisfying the conditions in theorem A and give the extremal graph. The join of disjoint graphs G and H is the graph obtained from G U H by joining any vertex of G and any vertex of H, and HI C G C. H means that graph G is isomorphic to a subgraph of H containing graph HI.Theorem 2.1 Suppose G is a 3-connected graph with n vertices and d 5 is an integer. Let x and y be two distinct vertices of G with d(v) d for all 2d and G contains no (x, y)-cycle of length greater than 2rf,then We generalize Theorem B to weighted graphs and get the impl...