The k-subconnectedness of planar graphs

Abstract

A graph G with at least 2k vertices is called k-subconnected if, for any 2k vertices x1,x2,⋯,x2k in G, there are k independent paths joining the 2k vertices in pairs in G. In this paper, we prove that a k-connected planar graph with at least 2k vertices is k-subconnected for k=1,2; a 4-connected planar graph is k-subconnected for each k such that 1≤k≤ν/2, where v is the number of vertices of G; and a 3-connected planar graph G with at least 2k vertices is k-subconnected for k=4,5,6. The bounds of k-subconnectedness are sharp.

Keywords

• k-connected graph
• independent paths
• planar graph
• k-subconnected graph
• component