2012/04/09 by Nikoghosyan, Zh. G.
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1204.1961
We present eighteen exact analogs of six well-known fundamental Theorems (due to Dirac, Nash-Williams and Jung) in hamiltonian graph theory providing alternative compositions of graph invariants. In Theorems 1-3 we give three lower bounds for the length of a longest cycle C of a graph G in terms of minimum degree δ, connectivity κ and parameters p, c - the lengths of a longest path and longest cycle in G\backslash C, respectively. These bounds have no analogs in the area involving p and c as parameters. In Theorems 11 and 12 we give two Dirac-type results for generalized cycles including a number of fundamental results (concerning Hamilton and dominating cycles) as special cases. Connectivity invariant κ appears as a parameter in some fundamental results and in some their exact analogs (Theorems 3-10) in the following chronological order: 1972 (Chvátal and Erdös), 1981a (Nikoghosyan), 1981b (Nikoghosyan), 1985a (Nikoghosyan), 1985b (Nikoghosyan), 2000 (Nikoghosyan), 2005 (Lu, Liu, Tian), 2009 (Nikoghosyan), 2009a (Yamashita), 2009b (Yamashita), 2011a (Nikoghosyan), 2011b (Nikoghosyan).