On the problems of CF-connected graphs

Michal Staš, Juraj Valiska

Abstract


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.


Keywords


crossing number, optimal drawing, crossing sequence, connectivity, complete graph

Full Text:

PDF

DOI: 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

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

View EJGTA Stats