کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647106 | 1632409 | 2014 | 18 صفحه PDF | دانلود رایگان |
We denote the order, the independence number, the connectivity and the minimum degree sum of independent four vertices of a graph GG by n(G)n(G), α(G)α(G), κ(G)κ(G) and σ4(G)σ4(G), respectively. The circumference of a graph GG, denoted by c(G)c(G), is the length of a longest cycle in GG. We call a cycle CC of a graph GG a DkDk-cycle if the order of each component of G−V(C)G−V(C) is at most k−1k−1. Our goal is to accomplish the proof of the statement that if GG is a 44-connected graph, then c(G)≥min{σ4(G)−κ(G)−α(G)+1,n(G)}c(G)≥min{σ4(G)−κ(G)−α(G)+1,n(G)}. In order to prove this, we consider three conditions for the construction of the outside of a longest cycle: (i) If GG is a 33-connected graph and every longest cycle of GG is a D2D2-cycle, then c(G)≥min{σ4(G)−κ(G)−α(G)+1,n(G)}c(G)≥min{σ4(G)−κ(G)−α(G)+1,n(G)}. (ii) If GG is a 33-connected graph and every longest cycle is a D3D3-cycle and some longest cycle is not a D2D2-cycle, then c(G)≥σ4(G)−κ(G)−4c(G)≥σ4(G)−κ(G)−4. (iii) If GG is a 44-connected graph and some longest cycle is not a D3D3-cycle, then c(G)≥σ4(G)−8c(G)≥σ4(G)−8. For each condition, the lower bound of the circumference is sharp.
Journal: Discrete Mathematics - Volume 333, 28 October 2014, Pages 66–83