Existence Of A Kind Of Cycles And Paths In Connected Graphs

In this thesis, we consider only finite, undirected and simple graph G =(V,E) of order n.A Hamilton cycle (path) of a graph G is a cycle (path) that contains everyvertex of G. A graph G is said to be hamiltonian (traceable), if it containsa Hamilton cycle (path). The length of a longest cycle in G is called thecircumference of G and denoted by c(G). Hence G is hamiltonian if c(G) = n.G is called Hamilton-connected, if for every pair (a,b) of distinct vertices inV , there exists a Hamilton path in G with ends a and b.This thesis consists of 3 chapters. After an introductory chapter, in chapter2 we discuss the existence of a kind of cycles and paths in connected graphs.A graph H is said to be a minor of a graph G if H can be obtained from asubgraph of G by contracting edges. Note that every subgraph of a graph is alsoits minor. A well-known "minor theorem"states that in every set of infinitegraphs, there exist two such that one is a minor of the other. Dean conjecturedthat some cycle of a κ-connected (κ≥2) non-hamiltonian graph contains κindependent vertices and their neighbors. He also conjectured that some pathof a κ-connected (κ≥1) non-traceable graph contains κ+ 1 independentvertices and their neighbors. As noted by Dean in [5], the cases κ= 2, 3 of thefirst Conjecture have already been proved (see [7] and [14]). The case κ= 2of Dean's Conjectures follows easily from a proof given by Dirac [6] (see alsoExercise 10.27 in [13]), further, the cases κ= 1, 2 of the second Conjecture areeasy. By investigating the situation when two subsequent vertices on a longestcycle of κ-connected non-hamiltonian (non-traceable) graph G have neighborsoutside C, we prove that Dean's conjectures are true if n ≤3δ.In chapter 3, we supply a note on the circumference of 3-connected graphs.The question whether a graph is hamiltonian seems to be hard to answer. Upto now, no easily verifiable necessary and su?cient conditions for a graph to behamiltonian are known. Also, no satisfactory answer is known to the questionhow to decide whether a given graph contains a cycle of given length, or a cycleof a length exceeding a certain minimum. The fact that no easy conditions areknown for these properties, gives rise to a growing number of conditions thatare either necessary or su?cient for the existence of such cycles. A well-knownresult of Dirac [6] states that c(G) ≥min{2δ,n} provided G is 2-connected.This result was extended to graphs with higher connectivity. In [8], Jungproved that for 3-connected graphs c(G) = |C| ≥4δ? 5, if some componentH of G ? C is not hamilton-connected, where C is a longest cycle of G. Veryrecently, by weakening the condition on H, Jung and Vumar [12] proved thatfor 3-connected graph G, c(G) = |C| ≥2d(u)+2d(v)?5 for some independentvertices u and v in G, if some component H of G ? C is not strongly linkedin G (for the definition of "strongly linked"see chapter 1), moreover the strictinequality holds unless G belongs to some exceptional class of graphs. In thenote, we supply an explicit characterization of the exceptional class of graphsfor the above estimate of |C|.Mathematical subject classification: 05C38...