Mathematics – Combinatorics
Scientific paper
2008-09-03
Mathematics
Combinatorics
32 pages
Scientific paper
Four basic Dirac-type sufficient conditions for a graph $G$ to be hamiltonian are known involving order $n$, minimum degree $\delta$, connectivity $\kappa$ and independence number $\alpha$ of $G$: (1) $\delta \geq n/2$ (Dirac); (2) $\kappa \geq 2$ and $\delta \geq (n+\kappa)/3$ (by the author); (3) $\kappa \geq 2$ and $\delta \geq \max\lbrace (n+2)/3,\alpha \rbrace$ (Nash-Williams); (4) $\kappa \geq 3$ and $\delta \geq \max\lbrace (n+2\kappa)/4,\alpha \rbrace$ (by the author). In this paper we prove the reverse version of (4) concerning the circumference $c$ of $G$ and completing the list of reverse versions of (1)-(4): (R1) if $\kappa \geq 2$, then $c\geq\min\lbrace n,2\delta\rbrace$ (Dirac); (R2) if $\kappa \geq 3$, then $c\geq\min\lbrace n,3\delta -\kappa\rbrace$ (by the author); (R3) if $\kappa\geq 3$ and $\delta\geq \alpha$, then $c\geq\min\lbrace n,3\delta-3\rbrace$ (Voss and Zuluaga); (R4) if $\kappa\geq 4$ and $\delta\geq \alpha$, then $c\geq\min\lbrace n,4\delta-2\kappa\rbrace$. To prove (R4), we present four more general results centered around a lower bound $c\geq 4\delta-2\kappa$ under four alternative conditions in terms of fragments. A subset $X$ of $V(G)$ is called a fragment of $G$ if $N(X)$ is a minimum cut-set and $V(G)-(X\cup N(X))\neq\emptyset$.
No associations
LandOfFree
Long cycles in graphs through fragments 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 Long cycles in graphs through fragments, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Long cycles in graphs through fragments will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-141123