On the Problems of <inline-formula><math display="inline"><semantics><mi mathvariant="bold-script">CF</mi></semantics></math></inline-formula>-Connected Graphs for <i>K_l,m,n</i>

Abstract

A connected graph, G, is Crossing Free-connected (CF-connected) if there is a path between every pair of vertices with no crossing on its edges for each optimal drawing of G. We conjecture that a complete tripartite graph, Kl,m,n, is CF-connected if and only if it does not contain any of the following as a subgraph: K1,2,7, K1,3,5, K1,4,4, K2,2,5, K3,3,3. We examine the idea that K1,2,7, K1,3,5, K1,4,4, and K2,2,5 are the first non-CF-connected complete tripartite graphs. The CF-connectedness of Kl,m,n with l,m,n≥3 is dependent on the knowledge of crossing numbers of K3,3,n. In this paper, we prove various results that support this conjecture.

Keywords

• crossing number
• crossing sequence
• connectivity
• complete tripartite graph