Algorithm for two disjoint long paths in 2 -connected graphs

In this paper, we prove that 2 -connected graphs have either a dominating path or two disjoint paths, wherein the length of the two paths is bounded by the minimum among n and a parameter defined on the neighborhood condition of any four independent vertices of the graph.

Authors

• Shan Zhou
• Hao Li Shanghai Artificial Intelligence Laboratory & Northwestern Polytechnical University
• Guanghui Wang East China Normal University

Keywords

• Path
• Degree sum
• Dominating path