Article Per Year (5 Year)
p-Index From 2021 - 2026
0.23
P-Index
This Author published in this journals
All Journal Electronic Journal of Graph Theory and Applications (EJGTA)
Juraj Valiska
Technical University of Košice
Electrical & Electronics Engineering

Published : 1 Documents Claim Missing Document
Claim Missing Document
Check
Articles

Found 1 Documents
Search

 1 
On the problems of CF-connected graphs Michal Staš; Juraj Valiska
Electronic Journal of Graph Theory and Applications (EJGTA) Vol 11, No 2 (2023): Electronic Journal of Graph Theory and Applications
Publisher : GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.5614/ejgta.2023.11.2.12

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.
Co-Authors Michal Staš