Small cycles and 2-factor passing through any given vertices in graphs

• Published in: Journal of applied mathematics & computing 2010-12, Vol.34 (1-2), p.485-493
• Main Author: Dong, Jiuying
• Format: Article
• Language: English
• Subjects: Computation; Computational Mathematics and Numerical Analysis; Computer science; Graphs; Mathematical and Computational Engineering; Mathematical models; Mathematics; Mathematics and Statistics; Mathematics of Computing; Networks; Theory of Computation
• ISSN: 1598-5865; 1865-2085
• DOI: 10.1007/s12190-009-0333-7

The theory of vertex-disjoint cycles and 2-factor of graphs has important applications in computer science and network communication. For a graph G , let σ 2 ( G ):=min { d ( u )+ d ( v )| uv ∉ E ( G ), u ≠ v }. In the paper, the main results of this paper are as follows: Let k ≥2 be an integer and G be a graph of order n ≥3 k , if σ 2 ( G )≥ n +2 k −2, then for any set of k distinct vertices v 1 ,…, v k , G has k vertex-disjoint cycles C 1 , C 2 ,…, C k of length at most four such that v i ∈ V ( C i ) for all 1≤ i ≤ k . Let k ≥1 be an integer and G be a graph of order n ≥3 k , if σ 2 ( G )≥ n +2 k −2, then for any set of k distinct vertices v 1 ,…, v k , G has k vertex-disjoint cycles C 1 , C 2 ,…, C k such that: v i ∈ V ( C i ) for all 1≤ i ≤ k . V ( C 1 )∪ ⋅⋅⋅ ∪ V ( C k )= V ( G ), and | C i |≤4, 1≤ i ≤ k −1. Moreover, the condition on σ 2 ( G )≥ n +2 k −2 is sharp.