Results 1 to 10 of about 284,407 (269)
Counting Hamiltonian Cycles in 2-Tiled Graphs
Mathematics, 2021 In 1930, Kuratowski showed that K3,3 and K5 are the only two minor-minimal nonplanar graphs. Robertson and Seymour extended finiteness of the set of forbidden minors for any surface.
Alen Vegi Kalamar +2 more
doaj +1 more source
Minor-monotone crossing number [PDF]
Discrete Mathematics & Theoretical Computer Science, 2005 The minor crossing number of a graph $G$, $rmmcr(G)$, is defined as the minimum crossing number of all graphs that contain $G$ as a minor. We present some basic properties of this new minor-monotone graph invariant.
Drago Bokal +2 more
doaj +1 more source
The crossing numbers of join products of eight graphs of order six with paths and cycles
Karpatsʹkì Matematičnì Publìkacìï, 2023 The crossing number $\mathrm{cr}(G)$ of a graph $G$ is the minimum number of edge crossings over all drawings of $G$ in the plane. The main aim of this paper is to give the crossing numbers of the join products of eight graphs on six vertices with paths ...
M. Staš
doaj +1 more source
Odd Crossing Number and Crossing Number Are Not the Same [PDF]
Discrete & Computational Geometry, 2006 The crossing number \(\text{cr}(G)\) of a graph \(G\) is the minimum number of edge crossings, taken over all drawing of \(G\) in the plane. Similarly \(\text{per}(G)\) (respectively \(\text{ocr}(G)\)) denotes the minimum number of pairs of edges which cross at least once (respectively an odd number of times), over all drawings of \(G\) in the plane ...
Michael J. Pelsmajer +2 more
openaire +4 more sources
The crossing number of the generalized Petersen graph P(3k,k) in the projective plane
AKCE International Journal of Graphs and Combinatorics, 2023 The crossing number of a graph G in a surface Σ, denoted by [Formula: see text], is the minimum number of pairwise intersections of edges in a drawing of G in Σ. Let k be an integer satisfying [Formula: see text], the generalized Petersen graph [Formula:
Jing Wang, Zuozheng Zhang
doaj +1 more source
On the crossing numbers of join products of W_{4}+P_{n} and W_{4}+C_{n} [PDF]
Opuscula Mathematica, 2021 The crossing number \(\mathrm{cr}(G)\) of a graph \(G\) is the minimum number of edge crossings over all drawings of \(G\) in the plane. The main aim of the paper is to give the crossing number of the join product \(W_4+P_n\) and \(W_4+C_n\) for the ...
Michal Staš, Juraj Valiska
doaj +1 more source
On the problems of CF-connected graphs
Electronic Journal of Graph Theory and Applications, 2023 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.
Michal Staš, Juraj Valiska
doaj +1 more source
On the Decay of Crossing Numbers [PDF]
Journal of Combinatorial Theory, Series B, 2007 Let \(\text{cr}(G)\) denote the crossing number of the graph \(G\). \textit{B. Richter} and \textit{C. Thomassen} [J. Comb. Theory, Ser. B 58, 217--224 (1993; Zbl 0733.05035)] conjectured that there is a constant \(c\) such that every graph \(G\) with crossing number \(k\) has an edge \(e\) such that \(\text{cr}(G-e)\geq k-c\sqrt{k}\), and showed that ...
Jacob Fox, Csaba D. Tóth
openaire +2 more sources
Degenerate Crossing Numbers [PDF]
Discrete & Computational Geometry, 2006 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
János Pach, Géza Tóth 0001
openaire +2 more sources
The crossing numbers of join products of four graphs of order five with paths and cycles [PDF]
Opuscula Mathematica, 2023 The crossing number \(\mathrm{cr}(G)\) of a graph \(G\) is the minimum number of edge crossings over all drawings of \(G\) in the plane. In the paper, we extend known results concerning crossing numbers of join products of four small graphs with paths ...
Michal Staš, Mária Timková
doaj +1 more source