Mathematics – Combinatorics
Scientific paper
2012-04-09
Mathematics
Combinatorics
11 pages
Scientific paper
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 $\delta$, connectivity $\kappa$ and parameters $\bar{p}$, $\bar{c}$ - the lengths of a longest path and longest cycle in $G\backslash C$, respectively. These bounds have no analogs in the area involving $\bar{p}$ and $\bar{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 $\kappa$ appears as a parameter in some fundamental results and in some their exact analogs (Theorems 3-10) in the following chronological order: 1972 (Chv\'{a}tal and Erd\"{o}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).
No associations
LandOfFree
My Research Visiting Card in Hamiltonian Graph Theory does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with My Research Visiting Card in Hamiltonian Graph Theory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and My Research Visiting Card in Hamiltonian Graph Theory will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-652543