### On the problems of CF-connected graphs

#### Abstract

The crossing number *c**r*(*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 *K*_{n} is *C**F*-connected if and only if it does not contain a subgraph of *K*_{8}, where a connected graph *G* is *C**F*-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 *K*_{n} for any *n* ≤ 12, and by assuming the Harary-Hill’s Conjecture that *c**r*(*K*_{n})=*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.

#### Keywords

#### Full Text:

PDFDOI: http://dx.doi.org/10.5614/ejgta.2023.11.2.12

#### References

B.M. Ábrego, O. Aichholzer, S. Fernández-Merchant, P. Ramos and B. Vogtenhuber, Non-shellable drawings of Kn with few crossings, CCCG 2014 Halifax, Nova Scotia, August 11–13 (2014).

J. Balogh, B. Lidický and G. Salazar, Closing in on Hill’s Conjecture, SIAM J. Discrete Math. 33(3) (2019), 1261–1276.

R.K. Guy, A combinatorial problem, Nabla (Bull. Malayan Math. Soc.) 7 (1960), 68–72.

F. Harary and A. Hill, On the number of crossings in a complete graph, Proc. Edinburgh Math. Soc. 13 (1963), 333–338.

M. Klešč, The crossing numbers of join of the special graph on six vertices with path and cycle, Discrete Math. 310(9) (2010), 1475–1481.

S. Pan and R.B. Richter, The crossing number of K11 is 100, J. Graph Theory 56(2) (2007), 128–134.

R.B. Richter and C. Thomassen, Relations Between Crossing Numbers of Complete and Complete Bipartite Graphs, The American Mathematical Monthly 104(2) (1997), 131–137.

M. Staš and J. Valiska, On problems of CF-connected graphs for Km, n. Bull. Aust. Math. Soc. 104(2) (2021), 203-210.

### Refbacks

- There are currently no refbacks.

ISSN: 2338-2287

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.