On the problems of CF-connected graphs

Michal Staš (Technical University of Košice)
Juraj Valiska (Technical University of Košice)

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 11, No 2 (2023): Electronic Journal of Graph Theory and Applications

The crossing number cr(G) of a graph G is the minimum number of edge crossings over all drawings of G in the plane, and the optimal drawing of G is any drawing at which the desired minimum number of crossings is achieved. We conjecture that a complete graph Kn is CF-connected if and only if it does not contain a subgraph of K8, where a connected graph G is 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 establish the validity of this Conjecture for the complete graphs Kn for any n ≤ 12, and by assuming the Harary-Hill’s Conjecture that cr(Kn)=H(n)=1/4⌊n/2⌋⌊n − 1/2⌋⌊n − 2/2⌋⌊n − 3/2⌋ is also valid for all n > 12. The proofs of this paper are based on the idea of a new concept of a crossing sequence.