2012/04/09 by Zh. G. Nikoghosyan, Nikoghosyan, Zh. G.
Computer Science · Mathematics · #Advanced Graph Theory Research #Backslash #Combinatorics #Combinatorics (math.CO) #Discrete mathematics #FOS: Mathematics #Graph #Graph theory #Graph theory and applications #Hamiltonian (control theory) #Hamiltonian path #Interconnection Networks and Systems #Invariant (physics) #Mathematical physics #Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1204.1961
published in arXiv (Cornell University) (Cornell University) · 11 pages
arxiv created 2012/04/09 · openalex publication_date 2012/04/09 · arxiv updated 2012/04/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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).