Path Factors and Neighborhoods of Independent Sets in Graphs

• Published in: Acta Mathematicae Applicatae Sinica 2023-04, Vol.39 (2), p.232-238
• Main Author: Zhou, Si-zhong
• Format: Article
• Language: English
• Subjects: Apexes; Applications of Mathematics; Graph theory; Integers; k factors; Math Applications in Computer Science; Mathematical and Computational Physics; Mathematics; Mathematics and Statistics; Real numbers; Theoretical
• ISSN: 0168-9673; 1618-3932
• DOI: 10.1007/s10255-022-1096-2

A path-factor is a spanning subgraph F of G such that every component of F is a path with at least two vertices. Let k ≥ 2 be an integer. A P ≥ k -factor of G means a path factor in which each component is a path with at least k vertices. A graph G is a P ≥ k -factor covered graph if for any e ∈ E ( G ), G has a P ≥ k -factor including e . Let β be a real number with and k be a positive integer. We verify that (i) a k -connected graph G of order n with n ≥ 5 k + 2 has a P ≥3 -factor if ∣ N G ( I )∣ > β ( n −3 k − 1) + k for every independent set I of G with ∣ I ∣ = ⌊ β (2 k + 1)⌋; (ii) a ( k + 1)-connected graph G of order n with n ≥ 5 k + 2 is a P ≥3 -factor covered graph if ∣ N G ( I )∣ > β ( n − 3 k − 1) + k + 1 for every independent set I of G with ∣ I ∣ = ⌊ β (2 k + 1)⌋.