Cyclic Permutations in Determining Crossing Numbers

Klešč, Marián; Staš, Michal

Geodesic

Parcourir par

Cyclic Permutations in Determining Crossing Numbers

Klešč, Marián ; Staš, Michal

Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 4, pp. 1163-1183

Voir la notice de l'article provenant de la source Library of Science

Résumé

The crossing number of a graph G is the minimum number of edge crossings over all drawings of G in the plane. Recently, the crossing numbers of join products of two graphs have been studied. In the paper, we extend know results concerning crossing numbers of join products of small graphs with discrete graphs. The crossing number of the join product G*+ D_n for the disconnected graph G* consisting of five vertices and of three edges incident with the same vertex is given. Up to now, the crossing numbers of G + D_n were done only for connected graphs G. In the paper also the crossing numbers of G*+ P_n and G* + C_n are given. The paper concludes by giving the crossing numbers of the graphs H + D_n, H + P_n, and H + C_n for four different graphs H with |E(H)| ≤ |V (H)|. The methods used in the paper are new. They are based on combinatorial properties of cyclic permutations.

Keywords: graph, drawing, crossing number, join product, cyclic permutation

@article{DMGT_2022_42_4_a9,
     author = {Kle\v{s}\v{c}, Mari\'an and Sta\v{s}, Michal},
     title = {Cyclic {Permutations} in {Determining} {Crossing} {Numbers}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1163--1183},
     publisher = {mathdoc},
     volume = {42},
     number = {4},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a9/}
}

TY  - JOUR
AU  - Klešč, Marián
AU  - Staš, Michal
TI  - Cyclic Permutations in Determining Crossing Numbers
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 1163
EP  - 1183
VL  - 42
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a9/
LA  - en
ID  - DMGT_2022_42_4_a9
ER  -

%0 Journal Article
%A Klešč, Marián
%A Staš, Michal
%T Cyclic Permutations in Determining Crossing Numbers
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 1163-1183
%V 42
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a9/
%G en
%F DMGT_2022_42_4_a9

Klešč, Marián; Staš, Michal. Cyclic Permutations in Determining Crossing Numbers. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 4, pp. 1163-1183. http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a9/