On the CF-Connectedness of Complete Bipartite Graphs with One Edge Removed

Abstract

The study of graph connectedness is a central topic in graph theory, with CF-connectedness being a specialized property of interest. A simple graph is CF-connected if it is connected and, in each of its optimal drawings, any two of its distinct vertices can be connected by a path consisting of uncrossed edges. This paper explores the CF-connectedness of complete bipartite graphs with one edge removed, denoted as Km,n∖e, where Km,n is a complete bipartite graph with partite sets of sizes m and n, while e is an arbitrary edge. We conjecture that Km,n∖e is CF-connected if and only if it contains no subgraph isomorphic to K3,7∖e or K4,5∖e. We verify this conjecture unconditionally for Km,n∖e with min{m,n}≤5. We also prove unconditionally that cr(K6,6∖e)=32, thereby confirming Chia and Lee’s conjecture in this case and showing that K6,6∖e is not CF-connected. For the remaining cases with larger partite sets, our results are conditional on Chia and Lee’s conjectured formula cr(Km,n∖e)=m2m−12n2n−12−m−12n−12. Assuming this formula, the proposed characterization of CF-connectedness extends to these cases.