Beschreibung

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…