Hamiltonian Cycles in Cerain Graphs and Out-arc Pancylic Vertices in Tournaments

Introduction In this thesis, we only consider finite graphs without loops and multiple edges. At this point, we introduce some definitions and notations as well as some well-known results of Hamiltonian graphs. For those not defined here we refer to [21]. The definitions and notations of digraphs will be introduced in Chapter 5. Let G = (V (G),E(G)) be a graph. The notations |V (G)| and |E(G)| are called the order and the size of G, respectively. For a vertex u of G and a subgraph H of G, the subset { v 2 V (H) | uv 2 E(G)} is defined as the neighborhood of u in H, denoted by NH(u); |NH(u)| is the degree of u with respect to H, denoted by dH(u). If there is no confusion, the degree dG(u) and the neighborhood NG(u) of u are simply denoted by d(u) and N(u), respectively. Sometimes we also use N[u] to denote the set N(u) [ {u}. The set of all edges incident with u is denoted by IG(u) or I(u). Note that |IG(u)| = dG(u). The symbols ¢(G), ±(G), !(G), ·(G) and ®(G) denote the maximum degree, the minimum degree, the number of components, the connectivity and the independence number of G, respectively…