We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
On the problems of CF-connected graphs.
- Authors
Staš, Michal; Valiska, Juraj
- 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.
- Subjects
GRAPH connectivity; PLANAR graphs; COMPLETE graphs; RAMSEY numbers; LOGICAL prediction
- Publication
Electronic Journal of Graph Theory & Applications, 2023, Vol 11, Issue 2, p491
- ISSN
2338-2287
- Publication type
Article
- DOI
10.5614/ejgta.2023.11.2.12